# 451 - Sort Characters By Frequency

解法一 - Max heap

我們可以先統計每個字母的 freq，然後把 <char, freq> 的 pair 放進 max heap，之後只要依序把最高 freq 的 char append 到 string 就好。

class Solution {
public:    
    string frequencySort(string s) {
        // Calculate frequency
        unordered_map<char, int> freqMap;
        for(auto &c: s) {
            freqMap[c]++;
        }

        // Push into max heap
        priority_queue<pair<char,int>, vector<pair<char,int>>, comp> maxHeap;
        for(auto& p: freqMap) {
            maxHeap.push(p);
        }

        // Build result string
        string res;
        while(!maxHeap.empty()) {
            for(int i = 0; i < maxHeap.top().second; ++i) {
                res += maxHeap.top().first;
            }
            maxHeap.pop();
        }

        return res;
    }

private:
    struct comp {
        bool operator() (const pair<char,int>& p1, const pair<char,int>& p2) {
            return p1.second < p2.second;
        }
    };
};

解法二 - 先把各字母的 freq 算出來，根據 freq 排序

class Solution {
public:    
    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;
    }
};