Sort Characters By Frequency

Given a string s, sort it in decreasing order based on the frequency of the characters. Return the sorted string (any valid answer is accepted).

Practice Link

Intuition#

Two steps:

1. Count frequencies — use a hash map to count how many times each character appears.
2. Output in decreasing frequency order — use a max-heap ordered by frequency; pop the most frequent character and append it freq times to the result.

The key insight is that the heap needs to order by frequency (int), not by character value. The pair type must be pair<int, char> — frequency first so the heap sorts on it.

Solution — Max-Heap#

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

        // max-heap ordered by frequency (int first)
        priority_queue<pair<int, char>> pq;
        for (auto& [ch, f] : freqMap)
            pq.push({f, ch});

        string res;
        while (!pq.empty()) {
            auto [freq, c] = pq.top();
            pq.pop();
            res += string(freq, c);  // append character freq times
        }
        return res;
    }
};

Time Complexity: O(n + d log d) — n to count, d log d to heapify and extract, where d ≤ 256
Space Complexity: O(d) for the map and heap

Trace — s = "tree"#

Frequency map: {t:1, r:1, e:2}

Heap (max by frequency):

Output: "eert" ✓ ("eetr" also valid)

Common pitfall — pair<char, int> vs pair<int, char>#

// wrong — frequency stored as the first element type (char)
priority_queue<pair<char, int>> pq;
pq.push({x.second, x.first});  // x.second is int frequency → narrowed to char

pair<char, int> makes the heap sort by the character's ASCII value, not frequency. Worse, storing an int frequency into a char field silently truncates it — for any character repeated ≥ 128 times the count wraps and the ordering breaks.

Always put frequency first as int:

priority_queue<pair<int, char>> pq;  // int first → heap orders by frequency

Bucket sort — O(n)#

Since frequency is bounded by s.size(), we can use bucket sort to avoid the O(d log d) heap entirely:

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

        // bucket[f] = characters that appear exactly f times
        vector<vector<char>> bucket(s.size() + 1);
        for (auto& [c, f] : freqMap)
            bucket[f].push_back(c);

        string res;
        for (int f = s.size(); f >= 1; f--)
            for (char c : bucket[f])
                res += string(f, c);
        return res;
    }
};

Time: O(n), Space: O(n)