10.md

Sort Characters by frequency

METHOD 1

string frequencySort(string s) {

        auto cmp=[](const pair<char,int>& a, const pair<char,int>& b)
        {
            return a.second<b.second;
        };
        unordered_map<char,int>m;
        priority_queue<pair<char,int>,vector<pair<char,int>>,decltype(cmp)>pq(cmp);

        for(int i=0;i<s.size();i++)
            m[s[i]]++;

        for(const auto & it:m)
        {
            pq.push({it.first,it.second});
        }

        string result="";
        while(!pq.empty())
        {
            pair<char,int>p=pq.top();
            pq.pop();
            result.append(p.second,p.first);

            //For each pair dequeued, the character p.first is appended p.second times to the result string.
            // This effectively adds characters in sorted order of their frequencies.
        }

        return result;
    }

METHOD 2

string frequencySort(string s) {
        // Initialize a hashmap to store character frequencies
        unordered_map<char, int> freqMap;
        
        // Count frequencies of each character
        for (char c : s) {
            freqMap[c]++;
        }
        
        // Custom comparator for priority queue to sort based on frequencies
        auto cmp = [&](const char& a, const char& b) {
            return freqMap[a] < freqMap[b];
        };
        
        // Priority queue to sort characters based on their frequencies
        priority_queue<char, vector<char>, decltype(cmp)> pq(cmp);
        
        // Push characters into priority queue
        for (const auto& entry : freqMap) {
            pq.push(entry.first);
        }
        
        // Build the result string by appending characters from priority queue
        string result = "";
        while (!pq.empty()) {
            char c = pq.top();
            pq.pop();
            result.append(freqMap[c], c);
        }
        
        return result;
    }