LeetCode 451. Sort Characters By Frequency

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    string frequencySort(string s) {
        unordered_map<char, int> m;
        for (auto &c : s) ++m[c];
        vector<pair<int, int>> v;
        for (auto &it : m) v.emplace_back(it);
        sort(v.begin(), v.end(), [](const pair<int, int> &a, const pair<char, int> &b) {
            return a.second > b.second;
        });
        string ans;
        for (auto &[c, n] : v)
            for (int i = 0; i < n; ++i)
                ans.push_back(c);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    string frequencySort(string s) {
        unordered_map<char, int> m;
        int maxFreq = 0;
        for (auto &c : s) maxFreq = max(maxFreq, ++m[c]);
        vector<string> buckets(maxFreq + 1);
        for (auto &[c, n] : m) buckets[n].push_back(c);
        string ans;
        for (int i = maxFreq; i; --i)
            for (auto &c : buckets[i])
                for (int k = 0; k < i; ++k)
                    ans.push_back(c);
        return ans;
    }
};