Sorting: Given a string, sort it by frequency of characters

Problem Statement:

Given a string, sort it by frequency of characters.
Capital letter and small letter are treated differently.

Example:

Input: str = "abbccc"

Output: "cccbba"

Solution Explanation:

Solution is very simple.

We will use map to store the char and the frequency.

Then move the map to vector such that vec.first = mp.second and vec.second = mp.first.

So that we can sort the array on frequency basis.

Then sort the vector.

Then copy all the value into the string result.

Time Complexity: O(1)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

string solution(string s) 
{   
    vector<pair<int,char>>vec;
    map<char,int>mp;

    for(int i=0;i<s.size();i++)
    {
        mp[s[i]]++;
    }

    for(auto i:mp)
    {
        vec.push_back({i.second,i.first});
    }

    sort(vec.rbegin(),vec.rend());

    string ans;
     
    for(auto i:vec)
    {
        for(int j=0;j<i.first;j++)
        {
            ans+= i.second;
        }
    }
    return ans;
}

int main() 
{
    string str = "aabbbcccc";

    cout<<solution(str);
    
    return 0;
}

Output

ccccbbbaa