C++: Sort Characters By Frequency

Thought Process

The core approach involves counting character frequencies and then sorting them in descending order. First, we use a hash map to count each character's frequency. Then, we use a max heap to efficiently retrieve characters with highest frequencies. Finally, we construct the result string by appending characters according to their frequencies from the heap. 

class Solution {
public:
    string frequencySort(string str) {
        
        unordered_map<char,int> freq;
        priority_queue<pair<int,char>> pq; // Max Heap
        string ans;

        for(char ch : str){
            freq[ch]++;
        }

        // Every element inside a map is a pair
        for(auto entity : freq){
            pq.push({entity.second,entity.first});
        }

        // Top element of the Heap would be the one with largest frequency.
        while(!pq.empty()){

            int frequency = pq.top().first;
            char ch = pq.top().second;
            for(int i=0;i<frequency;i++)
                ans.push_back(ch);

            pq.pop();
        }
        return ans;
    }
};

Code Complexity

Time Complexity: O(n log n)

Building the frequency map takes O(n) time, and heap operations take O(n log n) in the worst case.

Space Complexity: O(n)

We use extra space for the frequency map and priority queue, both proportional to the input size.

Code copied!