Sort Characters By Frequency

How it works

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.

Steps

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.

Complexity

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

Things to watch for

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.

from collections import Counter, defaultdict

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)

class Solution {
public:
    string frequencySort(string s) {
        unordered_map<char, int> count;
        for (char c : s) {
            count[c]++;
        }

        vector<vector<char>> buckets(s.size() + 1);
        for (auto& entry : count) {
            buckets[entry.second].push_back(entry.first);
        }

        string res;
        for (int i = s.size(); i > 0; i--) {
            for (char c : buckets[i]) {
                res += string(i, c);
            }
        }

        return res;
    }
};