Sort Characters By Frequency
Build a string where characters are sorted by descending frequency using a max-heap.
Sort Characters By Frequency
Problem: Given a string s, sort it so that characters with higher frequency come first. Characters with the same frequency can be in any relative order.
Example:
- Input:
s = "tree" - Output:
"eert"or"eetr"— 'e' appears 2×, 't' and 'r' appear 1× each
Note
Count how often each character appears, then build the output by repeating each character its count number of times — most frequent first.
How to Think About It
Starting point: Count frequencies with a hash map. Now you need to output characters in frequency-descending order — sort the unique characters by their count, then repeat each character count times. That's O(n log n) on up to 26 unique characters.
Why a max-heap works here: The output is built greedily — always append the most frequent remaining character, repeated its full count. A max-heap ordered by frequency gives you the most frequent character at the root. Pop it, append it to the result the right number of times, move to the next. O(n log k) where k ≤ 26.
Note: Since there are at most 26 unique characters, both approaches (sort or heap) are effectively O(n) in practice — the log factor is on at most 26 elements. The heap approach illustrates the greedy pattern more explicitly.
Brute Force
View Brute Force
Optimal — Max-Heap
View Optimal Solution
| Approach | Time | Space |
|---|---|---|
| Count + Sort | O(n log n) | O(n) |
| Count + Max-Heap | O(n log k) | O(n) |