Sort Characters By Frequency
A medium Heap interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Heap
- Sheets
- 1
- Core for
- 10 roles
The problem
Rearrange the characters of a string so that the most frequent character comes first, followed by the next most frequent, and so on, keeping each character's copies together. Characters with equal counts may appear in either order.
Example 1
- Input
- s = "tree"
- Output
- "eert"
- Why
- 'e' appears twice while 'r' and 't' each appear once. So 'e' must come first. "eert" is a valid answer; "eetr" is also valid.
Example 2
- Input
- s = "cccaaa"
- Output
- "cccaaa"
- Why
- 'c' and 'a' both appear three times. "cccaaa" and "aaaccc" are both valid.
Example 3
- Input
- s = "Aabb"
- Output
- "bbAa"
- Why
- 'b' appears twice, and both 'A' and 'a' appear once. All 'b' characters come first, followed by 'A' and 'a' in any order.
Constraints
- 1 <= s.length <= 5 * 10^5
- s consists of printable ASCII characters
How to think about it
Updated 2026-09-29The alphabet of characters is strictly bounded (at most 128 ASCII characters or 256 for extended byte sets), whereas the string length can reach half a million. Sorting the tiny set of unique characters by frequency is virtually free compared to touching the string itself.
Approaches, worst first
Max-heap of character frequencies
time O(n + C log C) · space O(C)
Count frequencies in a hash table or fixed array. Push character-frequency pairs into a max-heap. Repeatedly pop the highest frequency character and append its full repetition count to the result string.
Bucket sort by countWrite this one
time O(n) · space O(n)
Count characters, then place each character into an array of buckets indexed by frequency 1 to n. Iterate backwards from index n, repeating each character by its bucket index to reconstruct the string linearly.
Where people lose marks · 3
- Assuming characters are only lowercase English letters. The constraints specify printable ASCII, which includes uppercase letters, digits, spaces, and punctuation; case is distinct.
- Appending characters one by one in a naive string concatenation loop in languages with immutable strings, causing quadratic intermediate string allocations. Build with an array buffer or repeat method.
- Emitting a character only once instead of multiplying it by its frequency count.
The theory behind it
Heap — the ground this problem stands on. All Heap problems
What Heap is
A heap is a specialized tree that keeps only the single most extreme item at the very top. In a min-heap, every parent node is smaller than its children, so the smallest element in the entire collection sits immediately at the root. Unlike a binary search tree, a heap does not keep all items in full sorted order. It maintains only a partial order, making it fast at giving you the single smallest or largest item without spending time sorting everything else.
When to reach for it
Reach for a heap when a problem asks for the top k largest elements, the kth smallest value, or a running median from a stream of numbers. Signals include phrases like continuously finding the cheapest item, merging k sorted linked lists, or scheduling tasks with priorities. Whenever you need repeated access to the minimum or maximum value while items are added and removed dynamically, a priority heap is the tool.
How the pattern works
To find the k largest elements, keep a min-heap of fixed size k. Push incoming numbers into the heap; whenever the heap size grows past k, pop the top item, which is the smallest among them. After processing all elements, only the k largest remain. For a running median, balance two heaps: a max-heap holding the smaller half of numbers and a min-heap holding the larger half. In code, heaps are stored compactly as flat arrays where a node at index i has children at indices 2i plus 1 and 2i plus 2.
More Heap problems
Target Roles
Core requirement for 10 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .