Sort Characters By Frequency — LeetCode 451 Max-Heap Pattern

Problem Statement#

Given a string s, sort it in decreasing order based on the frequency of the characters. Return the rearranged string. If multiple answers are valid, return any.

Constraints:

• 1 <= s.length <= 5 * 10^5
• s consists of uppercase and lowercase English letters and digits

Input:  s = "tree"
Output: "eert"  (or "eetr")

Input:  s = "Aabb"
Output: "bbAa"  (or "bbaA")

Why This Problem Matters#

LeetCode 451 Sort Characters By Frequency is a high-frequency Amazon and Meta interview problem. It is the natural follow-up to Top K Frequent: count occurrences, then emit by descending frequency.

It tests three things: ability to count cleanly, ability to use a max-heap (or bucket sort) to extract by frequency, and string-building hygiene (use a list/array, not concatenation).

Keywords: "sort by frequency interview", "max heap string", "bucket sort character", "FAANG count and emit".

The Core Insight#

Count characters with a hash. Push (frequency, char) into a max-heap and pop, repeating each char frequency times into the result. Or use bucket sort: index by frequency, walk from high to low.

The heap approach is O(n + k log k) where k is alphabet size. Bucket sort is O(n). Both pass; bucket sort is slightly faster and the senior answer.

Visual Dry Run#

s = "tree". Counts: t=1, r=1, e=2.

Solution (Heap)#

import heapq
from collections import Counter
 
class Solution:
    def frequencySort(self, s):
        cnt = Counter(s)
        h = [(-c, ch) for ch, c in cnt.items()]
        heapq.heapify(h)
        out = []
        while h:
            c, ch = heapq.heappop(h)
            out.append(ch * (-c))
        return "".join(out)

var frequencySort = function(s) {
    const cnt = new Map();
    for (const ch of s) cnt.set(ch, (cnt.get(ch) || 0) + 1);
    const arr = [...cnt.entries()].sort((a, b) => b[1] - a[1]);
    const out = [];
    for (const [ch, c] of arr) out.push(ch.repeat(c));
    return out.join("");
};

Time: O(n + k log k) where k is unique characters (at most 62). Space: O(n) for the result.

Solution (Bucket Sort)#

from collections import Counter
 
class Solution:
    def frequencySortBucket(self, s):
        cnt = Counter(s)
        buckets = [[] for _ in range(len(s) + 1)]
        for ch, c in cnt.items():
            buckets[c].append(ch)
        out = []
        for i in range(len(buckets) - 1, 0, -1):
            for ch in buckets[i]:
                out.append(ch * i)
        return "".join(out)

Time: O(n). Space: O(n).

Common Mistakes#

• Using string concatenation in a loop — O(n^2). Use a list and "".join.
• Forgetting to multiply char by its frequency — emitting only one copy.
• Using += on a Python string in a hot loop.
• Treating uppercase and lowercase as the same character.
• Sorting the input string by char value instead of by count.

Interview Tips#

• Mention that since alphabet is small, the heap is essentially O(n).
• Bucket sort beats sorting in theory; in practice, both are fine for this constraint.
• Note that any valid order among tied frequencies is accepted.
• For Unicode, replace the bucket array with a hash; otherwise the alphabet is small.

Follow-up Questions#

• What if input is Unicode (millions of code points)? Heap still works; bucket sort needs a sparse map.
• Can you do this in O(n) with O(1) extra space? Yes — count in a 128-int array.
• What about preserving original order for ties? Stable sort by (-count, original_index).
• Streaming variant? Heap of (count, char), refresh on each new char.

Key Takeaways#

• LeetCode 451 reduces to count then emit by descending count.
• A max-heap on (count, char) works in O(n + k log k).
• Bucket sort by frequency runs in O(n).
• Always build the output with a list and join, never string concatenation.
• The alphabet is small (at most 62), so heap and bucket sort are both fast.
• Multiple valid orderings exist; ties can be broken arbitrarily.
• Generalizes to Reorganize String (LC 767) which uses the same heap pattern with adjacency constraint.