Sort Characters By Frequency — Editorial

Opening the reading…

Intuitionthe required order is determined by groups, not individual characters

The string is sorted by how often each character appears, so every copy of one character belongs together in the answer. First count the copies of each character. If a character appears 5 times, its entire group has priority over every character appearing 4 times, regardless of the characters' alphabetical order.

A character's frequency can be at most n, where n is the string length. That gives a direct index for every group: bucket[f] stores all characters appearing f times, already repeated f times. Reading the buckets from n down to 1 produces the required order without comparing characters against one another.

Each bucket stores complete character groups, so the final scan needs no comparisons.

Approach

Count every character in an unordered map, because the answer depends on frequency and not on the character's position in the input.

Create n + 1 buckets indexed by frequency, because no character can occur more than n times and bucket[f] must be a valid destination for a frequency of f.

For each character-frequency pair, append that character frequency times to bucket[frequency], because the final answer needs a complete group rather than one character that must be expanded later.

Scan bucket indices from n down to 1, because this visits larger frequencies before smaller ones and skips empty frequencies without doing any comparisons.

Append every nonempty bucket to the result, because each bucket is already internally valid and all characters in it have the same priority.

Return the result after the scan, because every input character was added to exactly one bucket and therefore the output contains the same characters with only their order changed.

Complexitythe bucket range is bounded by the input length

MEASURE	BOUND	WHY
Time	O(n)	Counting touches each of the n input characters once. Distributing characters writes exactly n output copies across the buckets, and scanning the n possible frequency indices visits each index once, so the total remains O(n).
Space	O(n) extra	The bucket array has n + 1 entries, and its stored character groups contain n copies in total; the result is required output and is excluded from the extra-space bound. The bound stays O(n) even when one character fills one bucket or every character occupies a different bucket.

Here n is the length of the input string. The alphabet has only uppercase letters, lowercase letters, and digits, so the number of distinct characters is bounded by a constant.

Annotated solutionC++ · bucket sort · complete character groups

CPPCount frequencies, place repeated groups into buckets, and concatenate buckets from largest to smallest frequency.

#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

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

        vector<string> bucket(s.size() + 1);
        for (const auto& entry : freq) {
            char c = entry.first;
            int count = entry.second;
            bucket[count].append(count, c);
        }

        string result;
        for (int count = static_cast<int>(s.size()); count >= 1; --count) {
            result += bucket[count];
        }
        return result;
    }
};

The append call is the key construction step: bucket[count].append(count, c) writes the whole group immediately, so the later scan only concatenates ready-made pieces. The loop starts at s.size() because that is the largest possible frequency, then moves downward. No tie-breaking is needed because the statement accepts any order among characters with equal frequency.

The heap alternativea natural choice when you do not want a bucket array

A max-heap can store one entry for each distinct character, ordered by frequency. Repeatedly remove the largest entry and append its character count times. This is a different arrangement, not an optimisation for this problem: it uses O(n log k) time and O(k) heap space, where k is the number of distinct characters, while the bucket method uses O(n) time and O(n) extra space.

CPPMax-heap alternative that removes the next highest-frequency character group each time.

#include <queue>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

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

        priority_queue<pair<int, char>> heap;
        for (const auto& entry : freq) {
            heap.push({entry.second, entry.first});
        }

        string result;
        while (!heap.empty()) {
            auto [count, c] = heap.top();
            heap.pop();
            result.append(count, c);
        }
        return result;
    }
};

The heap version is useful when frequencies are not naturally bounded by a manageable integer range, or when you want to process only the next highest-frequency group at a time. Here the frequency range is exactly 1 through n, so buckets avoid the heap's repeated logarithmic reordering and are the more direct fit.