Sorting Characters By Frequency

Problem Link:

1. https://www.codingninjas.com/studio/problems/sorting-characters-by-frequency_1263699?utm_source=striver&utm_medium=website&utm_campaign=a_zcoursetuf&leftPanelTabValue=PROBLEM

2. https://leetcode.com/problems/sort-characters-by-frequency/

Intiution:

1. By looking at the contraints, it was clear the complexity has to be nlogn.

2. Since they asked us to rearrange them in decreasing order that means higher frequency gets higher priority.

3. Thus we can use max priority queue to solve our problem.

Code:

// TIME COMPLEXITY : O(NLOGN)
// SPACE COMPLEXITY : O(u)+O(u) , u is number of unique characters,
//                    Since the maximum unique characters is 26+26+10
//                    We can say the space is constant

string sortByFrequency(int n, string& s)
{
    // Write Your Code here

    // To store the frequency of unique characters
    unordered_map<char,int> m;

    for(int i=0;i<n;i++){
        if(m.count(s[i])>0){
            m[s[i]]++;
            continue;
        }

        m[s[i]] = 1;
    }


    // To store the characters in decreasing order of frequency
    priority_queue<pair<int,char>> pq;

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

    // storing the result from priority queue
    string ans = "";

    while(!pq.empty()){
        int freq = pq.top().first;
        char ch = pq.top().second;
        pq.pop();

        for(int i=0;i<freq;i++){
            ans+=ch;
        }
    }

    return ans;
}