451. Sort Characters By Frequency - Explanation

Problem Link

1. Sorting

Intuition

To sort characters by frequency, we first need to know how often each character appears. Once we have the frequencies, we can sort the entire string using a custom comparator that prioritizes higher frequencies. Characters with the same frequency are sorted alphabetically for consistency.

Algorithm

1. Count the frequency of each character in the string.
2. Sort all characters using a custom comparator:
   • Higher frequency comes first.
   • If frequencies are equal, sort by character value for consistency.
3. Join the sorted characters into a string and return it.

class Solution:
    def frequencySort(self, s: str) -> str:
        count = Counter(s)
        sorted_chars = sorted(s, key=lambda x: (-count[x], x))
        return ''.join(sorted_chars)

Time & Space Complexity

• Time complexity: $O(n \log n)$
• Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.

---

2. Frequency Sort

Intuition

Instead of sorting all characters individually, we can sort the unique characters by their frequencies. This is more efficient because the number of unique characters is bounded (at most 62 for alphanumeric). After sorting the unique characters, we build the result by repeating each character according to its frequency.

Algorithm

1. Count the frequency of each character.
2. Create a list of (character, frequency) pairs for characters that appear at least once.
3. Sort this list by frequency in descending order (with alphabetical tiebreaker).
4. Build the result string by repeating each character by its frequency count.

class Solution:
    def frequencySort(self, s: str) -> str:
        count = [0] * 123
        for c in s:
            count[ord(c)] += 1

        freq = [(chr(i), count[i]) for i in range(123) if count[i] > 0]
        freq.sort(key=lambda x: (-x[1], x[0]))

        return ''.join(char * freq for char, freq in freq)

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$ for the output string.

---

3. Bucket Sort

Intuition

Bucket sort avoids comparison-based sorting entirely. Since frequencies range from 1 to n (the string length), we create buckets indexed by frequency. Each bucket holds characters that appear exactly that many times. By iterating from the highest frequency bucket down to the lowest, we naturally process characters in the required order.

Algorithm

1. Count the frequency of each character.
2. Create buckets where bucket[i] contains all characters with frequency i.
3. Iterate from the highest possible frequency (string length) down to 1.
4. For each character in the current bucket, append it to the result the appropriate number of times.
5. Return the result string.

class Solution:
    def frequencySort(self, s: str) -> str:
        count = Counter(s)  # char -> freq
        buckets = defaultdict(list)  # freq -> [char]

        for char, freq in count.items():
            buckets[freq].append(char)

        res = []
        for i in range(len(s), 0, -1):
            if i in buckets:
                for c in buckets[i]:
                    res.append(c * i)

        return "".join(res)

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

---

Common Pitfalls

Assuming Only Lowercase Letters

The input can contain uppercase letters and digits (ASCII 48-122), not just lowercase letters (97-122). Using an array of size 26 or only indexing by c - 'a' causes index out of bounds errors or incorrect results for uppercase letters and digits.

Not Grouping Same Characters Together

The output must have all occurrences of each character adjacent to each other. Simply sorting by frequency without ensuring character grouping can interleave different characters with the same frequency, producing invalid output.

Using an Unstable Sort Without Grouping

When sorting individual characters by frequency, an unstable sort may scatter characters with the same frequency. Either use bucket sort which naturally groups characters, or sort unique characters first and then build the result by repeating each character.