28. Sort Characters By Frequency

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

Example 1:

Input: s = "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: s = "cccaaa"
Output: "aaaccc"
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: s = "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: (Counting Frequency and sorting)

Approach: Counting Frequency Storing in a vector and sorting

class Solution
{
public:
    static bool cmp(pair<int, char> &a, pair<int, char> &b)
    {

        return a.first > b.first;
    }

    string frequencySort(string s)
    {

        unordered_map<char, int> m;

        for (int i = 0; i < s.length(); i++)
        {
            m[s[i]]++;
        }

        vector<pair<int, char>> v;

        for (auto itr = m.begin(); itr != m.end(); itr++)
        {
            v.push_back({itr->second, itr->first});
        }

        sort(v.begin(), v.end(), cmp);

        string res = "";
        for (int i = 0; i < v.size(); i++)
        {
           res.append(v[i].first, v[i].second);
        }

        return res;
    }
};

Time Complexity: O(n log n)

Solution: (Bucket Sort)

class Solution
{
public:
    string frequencySort(string s)
    {

        int n = s.length();
        unordered_map<char, int> m;

        for (int i = 0; i < s.length(); i++)
        {
            m[s[i]]++;
        }

        vector<string> bucket(n + 1, "");

        for (auto itr = m.begin(); itr != m.end(); itr++)
        {

            int count = itr->second;
            char ch = itr->first;
            bucket[count].append(count, ch);
        }

        string res = "";
        for (int i = n; i >= 0; i--)
        {
            res += bucket[i];
        }

        return res;
    }
};

Time Complexity: O(n)