Sort Characters By Frequency

 

Sort Characters By Frequency

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.

Example 3:

Input:
"Aabb"

Output:
"bbAa"

Explanation:
"bbaA" is also a valid answer, but "Aabb" is incorrect.
Note that 'A' and 'a' are treated as two different characters.

 

class Solution {
public:
     string frequencySort(string s) {
         if(s.empty())return "";
        int n=s.size(),cnt=1;
      
        sort(s.begin(),s.end());
          vector<pair<int,char> > v;
       
          for(int i=0;i<s.size()-1;++i)
          {

              if(s[i]==s[i+1])
              {
                  ++cnt;
              }else{
                  v.push_back({cnt,s[i]});
                  cnt=1;
              }
          }
        if(s[n-1]!=s[n-2])
            v.push_back({1,s[n-1]});
        else
             v.push_back({cnt,s[n-1]});
        string st="";
        sort(v.begin(),v.end());
        for(auto i=v.rbegin();i!=v.rend();++i)
        {
            for(int j=0;j<i->first;++j)
            {
                st+=i->second;
            }
        }
        return st;
    }
};

-------------------------------------------------------------------------------------------------------------------------------------

class Solution {
    /*
     
    */
public:
    string frequencySort(string s) {
        vector<pair<int,char>> charactors( 256 );
            for ( char &c : s )
            {
                charactors[c].first++;
                charactors[c].second = c;
            }

            sort( charactors.begin(), charactors.end(), greater<pair<int,char>>() );

            string ans;
            for ( int i = 0 ; i < 256 ; i++ )
            {
                if ( charactors[i].first == 0 ) break;
                ans.append( charactors[i].first, charactors[i].second );
            }
            return ans;
    }
};