Sort Characters By Frequency
Problem statement
You get a string s. Rearrange its characters so that whichever character
appears most often comes first, then the next most frequent, and so on down
to the least frequent — with every occurrence of a given character kept
together as one block. If several characters are tied in frequency, any
order between those tied groups is accepted, but characters must never be
interleaved: every occurrence of the same character has to sit in one
contiguous run.
Uppercase and lowercase versions of the same letter count as different
characters ('A' and 'a' are tracked separately), and digits are treated
the same way as letters — just another symbol to count and group.
Examples
Example 1
Input: s = "tree"
Output: "eert"
Explanation: 'e' appears twice, while 'r' and 't' each appear once, so 'e' must come first. "eetr" is also accepted, since the order between 'r' and 't' — the two tied, less-frequent characters — doesn't matter, as long as each is kept in one block.
Example 2
Input: s = "cccaaa"
Output: "aaaccc"
Explanation: 'c' and 'a' are tied at 3 occurrences each, so either "aaaccc" or "cccaaa" is valid. "cacaca" is rejected: even though it has the right counts, it splits the same character across separate runs instead of keeping each one together.
Example 3
Input: s = "Aabb"
Output: "bbAa"
Explanation: 'b' appears twice and must come first. 'A' and 'a' are different characters (capitalization matters) and both appear once, so either order between them is fine — "bbaA" is also accepted. "Aabb" is rejected because 'b' (the more frequent character) doesn't come first.
Hints
Approach
Optimal: Bucket sort by frequency
Intuition
A character's frequency can never exceed n (the length of the whole
string), so instead of sorting the distinct characters by frequency,
"sort" them for free by using their frequency directly as an array index.
Make an array of buckets, one slot per possible count from 0 to n. Drop
each distinct character into buckets[its count]. Then walk the buckets
from the highest possible count down to 1, and for every character found
in a bucket, write it out that many times. Because the buckets are visited
in a fixed, already-descending order, there's no comparison sorting step
at all — this is what pushes the time down from the k log k of the
better approach to a flat O(n).
Steps
- Count each character's frequency with a hash map.
- Create an array of
n + 1empty buckets, indexed by count (0 through n). - For each distinct character, append it to
buckets[its count]. - Walk
cntfromndown to1. For every character inbuckets[cnt], append that character to the resultcnttimes. - Return the built result.
Dry run
s = "tree" (n = 4)
| step | detail |
|---|---|
| counts | {t: 1, r: 1, e: 2} |
| buckets after distributing | buckets[1] = [t, r], buckets[2] = [e], all other buckets empty |
| walk cnt = 4, 3: | both empty, nothing appended |
| walk cnt = 2: | buckets[2] = [e] → append "e" × 2 → result so far: "ee" |
| walk cnt = 1: | buckets[1] = [t, r] → append "t" × 1, then "r" × 1 → result: "eetr" |
Final result: "eetr" — a valid answer (e first since it's most frequent,
then t and r in either order since they're tied).
Edge cases: an empty bucket at a given count is simply skipped — the inner
loop over buckets[cnt] does nothing when that count wasn't used by any
character. A string where every character is unique (all counts equal to
- puts everything into a single bucket,
buckets[1], and the walk from n down to 1 finds nothing until it reaches that one bucket.
Complexity
Time O(n) - no comparison sort at all. Counting is O(n), distributing distinct characters into buckets is O(k) (k ≤ 62), and building the output by walking the buckets is O(n), since the total number of characters written out across every bucket is exactly n.
Space O(n) - for the output, plus O(n) for the buckets array (indexed by every possible count from 0 to n, even though only a handful of slots are ever used).
from collections import Counter
class Solution:
def frequencySort(self, s: str) -> str:
counts = Counter(s)
n = len(s)
buckets = [[] for _ in range(n + 1)] # buckets[c] = chars that appear exactly c times
for ch, cnt in counts.items():
buckets[cnt].append(ch)
parts = []
for cnt in range(n, 0, -1):
for ch in buckets[cnt]:
parts.append(ch * cnt)
return "".join(parts)
if __name__ == "__main__":
print(Solution().frequencySort("tree"))
print(Solution().frequencySort("cccaaa"))
print(Solution().frequencySort("Aabb"))RecapThe whole problem in a few lines, for the night before
- Spot it: reorder a string so the most frequent characters come first
- Idea: count each character with a hash map, then sort by count (or use count buckets) and repeat each character that many times
- Cost: O(n log k) time with a sort, O(n) with buckets; O(n) space
- Trap: all copies of a character must stay together; 'a' and 'A' are different characters
Interview follow-ups
What if the string is too large to fit in memory, but you can stream through it once to count, and it's fine to do a second pass to build the output?
The counting step already only needs one linear pass and produces a small map (at most 62 entries) regardless of how long the string is, so that part scales fine as a stream. Building the output does need a second pass over the (now-known) counts to write each character's block, but that second pass can also be streamed out — for example written directly to a file or a network socket in bucket order — instead of being held as one giant string in memory at once.
How would this change if you only needed the top 5 most frequent characters, not the fully sorted string?
Skip the full sort or bucket walk once the top 5 are found — a fixed-size min-heap of size 5 (the same idea as the min-heap approach to Kth Largest Element in a Stream) lets you track only the 5 most frequent characters seen so far while scanning the count map once, in O(k log 5) instead of O(k log k) or a full O(n) bucket pass. This matters more as the alphabet size k grows (for example, if characters were arbitrary strings instead of single letters) — with a fixed 62-character alphabet the difference is negligible.
Frequently asked questions
The better and optimal approaches never sort individual character positions at all — they sort (or bucket) the small set of distinct characters, then write each one out as a whole block in one place. There's no way for two different characters to end up interleaved, because each one is only ever written once, as a complete run. The brute-force approach sorts every position in the original string directly, so if two different characters tie in frequency, a frequency-only key can't tell their positions apart — the tie-breaker is what forces same-character positions next to each other instead of leaving them wherever they started.
No — the checker only requires that (1) every character appears the correct number of times, (2) each character's occurrences are all contiguous, and (3) blocks are ordered from highest frequency to lowest. Whether 'a' comes before 'c' or 'c' comes before 'a' when they're tied at the same count is entirely up to the algorithm; nothing about hash map iteration order or bucket insertion order needs to be controlled for.
The buckets array is indexed by count, not by character — and a character's count can be as large as n itself (an entire string of one repeated character), so the array needs n + 1 slots to have room for every possible count value, even though only a handful of those slots ever end up holding anything. This is the classic space-for-time trade of a counting/bucket sort: it spends O(n) memory on mostly-empty buckets in exchange for avoiding any comparison sorting at all.
Ranking things by how often they occur — the most frequent error codes in a log window, the busiest endpoints in a traffic sample, the most-repeated alert type in an incident — is exactly this pattern: count occurrences, then present them ordered from most common to least, grouped rather than scattered.
