LeetCode 451: Sort Characters By Frequency

Problem Restatement

We are given a string s.

We need to rearrange its characters so that characters with higher frequency appear before characters with lower frequency.

The frequency of a character means how many times it appears in the string.

If two characters have the same frequency, their relative order does not matter. Any valid order is accepted.

For example:

s = "tree"

The character frequencies are:

The character e appears most often, so it should come first.

Valid answers include:

"eetr"
"eert"

Both are correct.

Input and Output

Function shape:

def frequencySort(s: str) -> str:
    ...

Examples

Example 1:

s = "tree"

Frequencies:

t -> 1
r -> 1
e -> 2

The character e appears twice, so it comes first.

Valid output:

"eetr"

Example 2:

s = "cccaaa"

Frequencies:

c -> 3
a -> 3

Both characters have the same frequency.

Valid outputs include:

"cccaaa"
"aaaccc"

Example 3:

s = "Aabb"

Frequencies:

A -> 1
a -> 1
b -> 2

The character b appears most often.

Valid output:

"bbAa"

Another valid output:

"bbaA"

Uppercase and lowercase characters are different.

So A and a are counted separately.

First Thought: Brute Force

A simple way is:

1. Count how many times each character appears.
2. Sort the whole string using each character’s frequency.
3. Return the sorted string.

In Python, this can be written directly:

class Solution:
    def frequencySort(self, s: str) -> str:
        freq = {}

        for ch in s:
            freq[ch] = freq.get(ch, 0) + 1

        chars = sorted(s, key=lambda ch: freq[ch], reverse=True)

        return "".join(chars)

This works because every character is ordered by its frequency.

For s = "tree", the frequencies are:

{
    "t": 1,
    "r": 1,
    "e": 2
}

Sorting by frequency places both e characters before t and r.

Problem With This Approach

This approach sorts all n characters.

If the length of the string is n, sorting costs:

O(n log n)

This is acceptable, but we can do better conceptually.

We do not need to sort every character occurrence individually. If a character appears many times, we can sort that character once, then repeat it in the output.

For example, in:

s = "eeeeeeeezzq"

we do not need to sort all eight e characters separately.

We only need to know:

e -> 8
z -> 2
q -> 1

Then build:

"eeeeeeeezzq"

Key Insight

The string can be compressed into character-frequency pairs.

Instead of sorting this:

["e", "e", "e", "e", "z", "z", "q"]

we sort this:

[("e", 4), ("z", 2), ("q", 1)]

Then we rebuild the answer by repeating each character according to its frequency.

This gives a clean three-step solution:

1. Count character frequencies.
2. Sort unique characters by frequency in descending order.
3. Build the answer string.

Algorithm

Create a hash map freq.

Scan the string once.

For each character ch, increment its count:

freq[ch] = freq.get(ch, 0) + 1

Then sort the character-frequency pairs by frequency from largest to smallest:

items = sorted(freq.items(), key=lambda item: item[1], reverse=True)

Finally, build the answer.

For each pair (ch, count), append:

ch * count

to the result.

Correctness

The hash map stores the exact frequency of every character in s.

After counting, each distinct character appears once in the map, together with the number of times it appeared in the original string.

Sorting the map entries by frequency places every character with a larger frequency before every character with a smaller frequency.

When we build the output, we append each character exactly count times. Since count is the original frequency of that character, the output contains exactly the same characters as the input.

Therefore, the returned string is a rearrangement of s, and its characters are ordered by decreasing frequency.

Complexity

Let:

n = len(s)
k = number of distinct characters in s

Since k <= n, this is also commonly written as:

O(n log n)

But O(n + k log k) is more precise.

Implementation

class Solution:
    def frequencySort(self, s: str) -> str:
        freq = {}

        for ch in s:
            freq[ch] = freq.get(ch, 0) + 1

        items = sorted(freq.items(), key=lambda item: item[1], reverse=True)

        parts = []
        for ch, count in items:
            parts.append(ch * count)

        return "".join(parts)

Code Explanation

We first create an empty hash map:

freq = {}

Then we count each character:

for ch in s:
    freq[ch] = freq.get(ch, 0) + 1

If the character has appeared before, its count increases.

If it has not appeared before, freq.get(ch, 0) gives 0, so its first count becomes 1.

Next, we sort the frequency table:

items = sorted(freq.items(), key=lambda item: item[1], reverse=True)

Each item looks like:

(character, frequency)

The key function:

lambda item: item[1]

means we sort by the frequency.

The argument:

reverse=True

means largest frequency first.

Then we build the result:

parts = []
for ch, count in items:
    parts.append(ch * count)

For example, if:

ch = "e"
count = 2

then:

ch * count

produces:

"ee"

Finally:

return "".join(parts)

combines all pieces into one string.

Testing

Because ties can have multiple valid outputs, tests should check frequencies rather than requiring only one exact string.

from collections import Counter

def is_valid_frequency_sort(original: str, result: str) -> bool:
    if Counter(original) != Counter(result):
        return False

    freq = Counter(original)

    for i in range(1, len(result)):
        if freq[result[i - 1]] < freq[result[i]]:
            return False

    return True

def run_tests():
    s = Solution()

    result = s.frequencySort("tree")
    assert is_valid_frequency_sort("tree", result)

    result = s.frequencySort("cccaaa")
    assert is_valid_frequency_sort("cccaaa", result)

    result = s.frequencySort("Aabb")
    assert is_valid_frequency_sort("Aabb", result)

    result = s.frequencySort("")
    assert is_valid_frequency_sort("", result)

    result = s.frequencySort("a")
    assert is_valid_frequency_sort("a", result)

    result = s.frequencySort("raaeaedere")
    assert is_valid_frequency_sort("raaeaedere", result)

    print("all tests passed")

run_tests()

Test meaning: