Sort Characters By Frequency
Rearrange a string so characters appear in blocks ordered by descending frequency.
Open on LeetCode ↗Intuition
It is tempting to sort the string's own characters by frequency, but that interleaves equal-frequency characters in whatever order they land, and the problem needs every copy of one character CONTIGUOUS. Sorting characters is the wrong object to sort. Count occurrences first, then order only the distinct characters by their count. Once the order of distinct characters is fixed, emit each one that many times in a row before moving to the next. The invariant is simple: nothing about placement is decided until counting is done.
Count, sort the distinct characters by count descending, then emit each one repeated. Sorting the 26-ish distinct keys rather than the string's characters is what keeps this near-linear in the input length.
Approach
Count occurrences
Walk the string once and build a frequency map from character to count, remembering the order characters first appear in so the trace stays readable. This is the only pass that reads the raw string.
Order the distinct characters
Sort just the distinct keys of the frequency map by descending count. This list is small, bounded by the alphabet size rather than the string length, which is what keeps the whole approach fast even on long strings.
Emit each character in one contiguous block
Walk the ordered distinct characters and append each one exactly its count number of times before moving to the next character. Because the sort happened on distinct characters, not on individual letters, every block stays together by construction.
Solution & live demo
Common pitfalls
Sorting the characters of the string
return ''.join(sorted(s, key=lambda c: -counts[c]))
ordered = sorted(counts, key=lambda c: -counts[c])
That's O(n log n) on the full string rather than O(k log k) on the distinct keys. It also relies on sort stability to keep equal-frequency characters grouped, which is fragile reasoning.
Building the result character by character
for c in ordered:
for _ in range(counts[c]): result.append(c)result.append(c * counts[c])
String repetition emits the whole run in one operation. The inner loop does the same work with per-character overhead and more code.
Sorting ascending
sorted(counts, key=lambda c: counts[c])
sorted(counts, key=lambda c: -counts[c])
The problem asks for decreasing frequency, so the most common character must come first. The negation (or reverse=True) is the whole ordering requirement.
Edge cases
the frequency map is empty, the loop over distinct characters does nothing, and the result is the empty string
every count is 1, so any order among them is a valid answer since ties break arbitrarily
a single distinct entry with a large count still emits correctly as one block
'A' and 'a' are different keys in the frequency map, since character equality is case-sensitive