Sort Characters By Frequency (LeetCode 451)

The problem

You get a string s. Rearrange it so that characters appear in order of decreasing frequency, with all copies of a character grouped together. If two characters have the same count, either may come first. Upper and lower case are different characters.

Input:  "tree"
Output: "eert"   ("eetr" is also accepted)

e appears twice, so it comes first; t and r appear once each, in either order.

How to think about it

Start with brute force. Sort the characters with a key of “how many times does this character appear in s?”, calling s.count(ch) for each. That’s O(n) per call and n calls, so O(n²), and it can still split equal-count characters into an interleaved order ("trtr"-style) unless you add a tie-breaker.

The key insight: count once, then sort the distinct characters, not the string. A hash map gives every character’s count in one O(n) pass. There are only k distinct characters (k ≤ 62 for letters and digits), so ordering them by count is cheap. Then emit each character count times. Grouping is automatic, because each character is written in one go.

Heap or not? The textbook heap version pushes (-count, char) for each distinct character and pops them in order. Counter.most_common() does the same job, returning (char, count) pairs sorted by count, highest first. Using it is fine in an interview, but be ready to explain it’s just a sort (or heap) over k items. For a guaranteed O(n), use bucket sort: a list indexed by count.

Which pattern is this? Frequency counting followed by ordering, the same front half as Top-K. The tell is “by frequency” in the question.

Approach

1. Count every character with a hash map.
2. Order the distinct characters by count, highest first.
3. For each one, write the character repeated count times.
4. Join the pieces into the answer.

Solution

from collections import Counter
def frequency_sort(s):
    cnt = Counter(s)                                         # char -> count, one pass
    return "".join(c * f for c, f in cnt.most_common())      # highest count first, each char grouped
# frequency_sort("tree") -> "eert" or "eetr" (e's first)

Dry run

On "tree":

t comes before r because most_common keeps first-seen order among equal counts.

Complexity

• Time: O(n + k log k), where k is the number of distinct characters. Counting is O(n), ordering k items is O(k log k), and building the output is O(n). Since k is bounded by the alphabet, that’s effectively O(n).
• Space: O(n) for the output string, plus O(k) for the counter.

Edge cases and pitfalls

• Case matters: "Aabb" gives "bbAa" or "bbaA". A and a are counted separately.
• All one character returns the string unchanged.
• Equal counts may come out in either order, as with "cccaaa" → "cccaaa" or "aaaccc". But each character must stay grouped: "cacaca" is wrong.
• Sorting the string with a count key (sorted(s, key=s.count)) is slow and doesn’t group ties. Count first.

Related problems

• Top K Frequent Elements (LeetCode 347): the same counting, then keep only the top k.
• Reorganize String (LeetCode 767): the same counts, but spread copies apart instead of grouping them.
• Group Anagrams (LeetCode 49): another problem built on character counts.