Sort Characters by Frequency

Problem

Sort the characters of a string so that the most frequent characters come first.

Constraints

• 1 ≤ s.length ≤ 5·10⁵

Approach — Heaps / Top-K

This is a Heaps / Top-K problem. The idea: use a heap so the min, max, or top-k element stays reachable in O(log n) per operation. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n log k) time.

Solution code

Python

class Solution:
    def frequencySort(self, s):
        from collections import Counter
        c = Counter(s)
        items = sorted(c.items(), key=lambda kv: (-kv[1], kv[0]))
        return ",".join("%s:%d" % (ch, n) for ch, n in items)

Java

class Solution {
    public String frequencySort(String s) {
        // Count each character.
        Map<Character, Integer> count = new HashMap<>();
        for (char ch : s.toCharArray()) {
            count.put(ch, count.getOrDefault(ch, 0) + 1);
        }

        // Max-heap of characters by their count.
        PriorityQueue<Character> heap = new PriorityQueue<>(
            (a, b) -> count.get(b) - count.get(a)
        );
        heap.addAll(count.keySet());

        // Append each character count times in descending order.
        StringBuilder sb = new StringBuilder();
        while (!heap.isEmpty()) {
            char ch = heap.poll();
            int freq = count.get(ch);
            for (int i = 0; i < freq; i++) {
                sb.append(ch);
            }
        }
        return sb.toString();
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.