Algorithm

Sort Characters By Frequency (Bucket Sort)

Sorting Pattern

Sort Characters By Frequency (Bucket Sort)

Given a string s, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string.

CONSTRAINTS
  • 1 <= s.length <= 5 * 10⁵
  • s consists of uppercase and lowercase English letters and digits.
EXAMPLE 1
Input: s = "tree"
Output: "eert"
'e' appears twice while 'r' and 't' both appear once. So 'e' must appear before both 'r' and 't'. 'eert' is also a valid answer.
EXAMPLE 2
Input: s = "cccaaa"
Output: "cccaaa"
Both 'c' and 'a' appear three times, so 'cccaaa' is valid. 'aaaccc' is also valid.
If two characters have the same frequency, does their relative order in the output matter?
No. For example, if 'a' and 'b' both appear twice, both 'aabb' and 'bbaa' are considered valid answers.
Are the characters case-sensitive?
Yes. 'A' and 'a' should be treated as two different characters with their own independent frequency counts.
Can the string contain digits or special characters?
Yes. The input can contain any ASCII characters including digits and letters.
The Core Insight

To sort by frequency, we first need to know how many times each character appears. A simple frequency map (O(N)) does this. But how do we sort those frequencies?

The Logic: What is Bucket Sort?

Bucket Sort is a distribution-based sorting algorithm. Think of it like a post office sorting mail into different bins based on zip codes.

1. The Distribution: You create a series of "buckets" (bins).
2. The Placement: You iterate through your data and place each item into a specific bucket based on a certain property (like its value or frequency).
3. The Gathering: Finally, you collect the items from the buckets in order.

The catch: To be efficient, you must be able to map your data to buckets in a way that preserves order. If you can do this, you avoid the cost of comparing every element against every other element.

Why it works for Frequency Sort

In this problem, the "property" we care about is frequency. We know that the frequency of any character must be between 1 and the total length of the string (N). This gives us a perfect, bounded range for our buckets.

> Technical Note: This is a Bucket Sort. Unlike H-Index where we just tally numbers, here each bucket must store a list of characters that share the same frequency. Since a bucket can hold multiple different characters (like 'a' and 'b' both appearing 3 times), we use a collection at each index.

The Bucket Strategy

The maximum frequency any character can have is n (the length of the string).
1. Create an array of "buckets" where buckets[i] is a list of all characters that appeared exactly i times.
2. Iterate through our frequency map and place each character into its corresponding bucket.
3. Iterate through the buckets from n down to 1, and for each character in the bucket, append it to our result string i times.

python
def frequencySort(s):
    # 1. Count frequencies
    counts = Counter(s)
    n = len(s)
    
    # 2. Map frequency -> characters
    buckets = [[] for _ in range(n + 1)]
    for char, freq in counts.items():
        buckets[freq].append(char)
        
    # 3. Build result from largest buckets
    res = []
    for freq in range(n, 0, -1):
        for char in buckets[freq]:
            res.append(char * freq)
            
    return "".join(res)
Visualizing the Buckets: "tree"

- Frequency Map: {'t': 1, 'r': 1, 'e': 2}
- Buckets:
- Bucket[2]: ['e']
- Bucket[1]: ['t', 'r']
- Result: "e" 2 + "t" 1 + "r" * 1 = "eetr"

Interactive Strategy Visualization

Visual Intuition

Watch the bubble sort process step-by-step.

5
0
3
1
8
2
4
3
2
4
STEP 1 / 23 • INIT

Starting Bubble Sort on a random array.

O(N log N) Sorting -> O(N) Bucket Sort