Day 21:LeetCode 30 Day May Challenges

Problem_statement21.txt

Given a string, sort it in decreasing order based on the frequency of characters.

Example 1:

Input:
"tree"

Output:
"eert"

Explanation:
'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.
Example 2:

Input:
"cccaaa"

Output:
"cccaaa"

Explanation:
Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer.
Note that "cacaca" is incorrect, as the same characters must be together.

sort_elements_by_frequency.cpp

class Solution {
public:
    /*
    bool mycomp(pair<int,char> a,pair<int,char> b){
        //non_increasing order
        return (a.first>b.first);
    }
    */
    string frequencySort(string s) {
        vector<pair<int,char>> v;
        unordered_map<char,int> mp;
        //int n = s.size();
        for(char x : s){
            mp[x]++;
        } 

        /*
        for(auto it=mp.begin(); it!=mp.end(); it++){
            v.push_back({it->second,it->first});
        }
        */
        for(auto p:mp){
            //v.push_back(make_pair(p.second,p.first));
            v.push_back({p.second,p.first});
        }
        //sort(v.begin(),v.end(),mycomp);
        sort(v.begin(),v.end(),[](pair<int,char> a,pair<int,char> b){return a.first>b.first;});
        string ans = "";
        for(auto p:v){
            int n=p.first;
            while(n--){
                ans+=p.second;
            }
        }
        return ans;
    }
};
//METHOD -2
//consumes a lot of space,if frequency of character is large like 42167989737
class Solution {
public:
    string frequencySort(string s) {
        unordered_map<char,int> freq;
        vector<string> bucket(s.size()+1, "");
        string res;
        
        //count frequency of each character
        for(char c:s) freq[c]++;
        //put character into frequency bucket
        for(auto& p:freq) {
            int n = p.second;
            char c = p.first;
            bucket[n].append(n, c);
            //fill
            //Appends n consecutive copies of character c.
        }
        //form descending sorted string
        //need s.size()+1 because we travel upto 1 and also we dont insert empty("") characters in vector
        for(int i=s.size(); i>0; i--) {
            if(!bucket[i].empty())
                res.append(bucket[i]);
        }
        return res;
    }
};