Sort Characters By Frequency

Given a string, sort it in decreasing order based on the frequency of characters.

Example 1: Input: "tree" Output: "eert"

Explanation: 'e' appears twice while 'r' and 't' both appear once. So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

Example 2: Input: "cccaaa" Output: "cccaaa"

Explanation: Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer. Note that "cacaca" is incorrect, as the same characters must be together.

Example 3: Input: "Aabb" Output: "bbAa"

Explanation: "bbaA" is also a valid answer, but "Aabb" is incorrect. Note that 'A' and 'a' are treated as two different characters.

Solution: Using sort

Time complexity: O(nlogn)

string frequencySort(string s) {
    int counts[256] = {0};
    for (char ch : s)
        ++counts[ch];
    sort(s.begin(), s.end(), [&](char a, char b) { 
        return counts[a] > counts[b] || (counts[a] == counts[b] && a < b); 
    });
    return s;
}

Solution: Counting sort / Bucket sort

The idea of this solution is to use hash map to store the frequency of each character, use vector to store chars with same frequence.

string frequencySort(string s) {
    unordered_map<char,int> freq;
    vector<string> bucket(s.size()+1, "");
    string res;

    //count frequency of each character
    for(char c:s) freq[c]++;

    //put character into frequency bucket
    for(auto& it:freq) {
        int n = it.second; // frequence
        char c = it.first; // character
        bucket[n].append(n, c);
    }

    //form descending sorted string
    for(int i=s.size(); i>0; i--) {
        if(!bucket[i].empty())
            res.append(bucket[i]);
    }
    return res;
}