Sort elements on basis of frequency in a string in C++

In this tutorial, we are going to discuss on how to sort elements on the basis of frequency in a given string in C++ and if the frequency of two characters is same then alphabetically smaller character will come first. These type of problem are useful from interview point of view and are asked in competitive programming contests also. So, let’s discuss the approach of doing such kind of problem.

What is map?

Map are the containers in which elements are assigned in a (key,value) pair. No two value can have the same key.

Syntax:-      map<data_type_key, data_type_value> map_name;




We will use map in this problem to find the frequency of each value in the given string where characters in string is key and frequency is value.

What is vector?

Vectors are dynamic arrays with the ability to resize as elements are inserted and deleted.

To insert an element in vector, we use push_back(value) and delete an element we use pop_back().

Syntax:-

vector_name.push_back( value );

vector_name.pop_back();

What is pair?

Pair container is defined in <utility> header file. Pair is used to combine two value which may be of different data_type.

To access an element from pair we use pair name followed by dot operator then first or second which value we want to access.

Syntax:

pair<char,int>p;

p.first=1;

p.second=’a’;

To make pair of two values we use make_pair( value1, value2 ).

How to sort vector in ascending order in C++

To sort vector in ascending order, we simply use

    sort ( vector_name.begin(), vector_name.end() );

How to sort vector in descending order?

To sort vector in descending order we use a third argument compare which is of boolean type and is defined by user.

     sort ( vector_name.begin(), vector_name.end(), compare );

bool compare( pair<data_type1, data_type2>pair_name1, pair<data_type1, data_type2>pair_name2)

{

return p1.second<p2.second;

}

C++ Code implementation of sorting elements on basis of frequency in a given string

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) c.begin(),c.end()
const int mod=1e9+7;
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;

string str;

ll i,j,n,t;

bool compare(pair<int,char>p1, pair<int,char>p2)
{
    if(p1.first==p2.first)
       return p1.second<p2.second;
       
       else
           return p1.first<p2.first;
}


   int main()
 {
    fast;
    
        cin>>t;
        
        while(t--)
        {
            string s;
              cin>>s;
              
             map<char,int>m;
              
                for(i=0;i<s.length();i++)
                {
                    m[s[i]]++;
                }
                
               vector<pair<int,char> >v;
               
                for(i=0;i<s.length();i++)
                {
                    v.pb(mp(m[s[i]],s[i]));
                }
                
                sort(v.begin(),v.end(),compare);
                
                for(i=0;i<v.size();i++)
                    cout<<v[i].second;
                    
                    cout<<endl;
        }
          
 }

INPUT

codespeedy

OUTPUT

copsyddeee

Thanks For Reading !!

We hope you have learned how to Sort elements on the basis of frequency in a given string in C++.

For any doubts please comment in the comment section below. Keep reading and stay tuned.

Also, read:


Leave a Reply

Your email address will not be published. Required fields are marked *