Sort Characters By Frequency | Leetcode #451

This video explains a very important programming interview question which is to rearrange the string in such a way that all the highest frequency characters occurs first followed by 2nd highest frequency characters and so on till the least frequent character. The new string must contain the same number of each unique character and the relative order of two unique characters with same frequency is not important. Therefore, we can have multiple answers to the same input string. I have shown the solution using a simple hash method using array of pairs. At the end of the video, i have explained the CODE and CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)

SIMILAR PROBLEMS:-

[arpitsahu]

In c++, you can also use append instead of the '+' operator. Its helps reduce the complexity and is easier to remember for a general use case scenario.

[vishnuvardhan-wqqi]

Same implementation struck to my mind. Thanks to your videos. Watching ur videos made me learn and analyse psuedo code faster than before

[rajeshbammidy]

Can be solved using PriorityQueue too, the question would have been interesting if they have mentioned stability/order of the characters matters

[ShubhamMahawar_Dancer_Actor]

we can solve it by using map<pair<char, int>> then more easy

[srutiverma]

class Solution {
public:
bool static comp(const pair<char, int>&a, const pair<char, int>&b){
if(a.second==b.second)
return a.first<b.first;
return a.second>b.second;
}
string frequencySort(string s) {
string str="";
map<char, int>m;
vector<pair<char, int>>v;
for(int i=0;i<s.length();i++){
m[s[i]]++;
}
for(auto i:m){
v.push_back(make_pair(i.first, i.second));
}
sort(v.begin(), v.end(), comp);
for(auto i:v){
while(i.second--)
str+=i.first;
}
return str;
}
};


Runtime: 8 ms, faster than 97.63% of C++ online submissions for Sort Characters By Frequency.
Memory Usage: 8.5 MB, less than 40.80% of C++ online submissions for Sort Characters By Frequency.

[subham-raj]

I feel you should have covered the Bucket Sort implementation.

[AnkitSingh-fwxy]

vector<pair<int, char>> hash('z'+1, {0, 0}) please explain whats is getting formed here?
What do I need to study for this Sir?

[fatimajaffal]

My approach have same time complexity but different space right?
class Solution {
public:
string frequencySort(string s) {
map<char, int> m;
vector<pair<char, int>>vec;
for (int i = 0; i < s.size(); i++)
m[s[i]]++;
for (auto i : m) vec.push_back({i.first, i.second});
string result = "";
int start = 0;
sort(vec.begin(), vec.end(), [](pair<char, int>elem1, pair<char, int>elem2){return elem1.second > elem2.second;});
for(auto i:vec){
result.insert(result.begin() + start, i.second, i.first);
start+= i.second;
}
return result;
}
};

[ritiksrivastava]

import string
class Solution:
def frequencySort(self, s: str) -> str:
dic={}
out=""
for i in s:
if i in dic:
dic[i]+=1
else:
dic[i]=1
q=dict(sorted(dic.items(), key=lambda dic:dic[1], reverse=True))
for i, j in q.items():
out+=i*j
return out

[MrAirnya]

omg, man
short and nice explanation
you are amazing

[Rahul-sxzo]

using sort stl, don't we need a third arguement, a call to an user defined explicit function in the sort() function. my question is how does sort here not sort the vector of pairs in ascending order? I'm a noobie (:

[newlearner]

Can you take solving sorting of alphanumeric string efficiently. Inputstr = “d4c3b2a1” Output: a1b2c3d4

[agileprogramming]

I am new to C++. I have one doubt. If it was sorted in ascending order using sort(hash.begin(), hash.end())
Then in the next loop how did you get the largest string to come first sir?

[madhav]

I think we need to sort the hash vector in descending order, right ? only then we get "eetr"

[sohinidey]

In python, dictionary will not be beneficial when I ll sort the string. Will i use 2d array ??

[noober]

After watching this I feel like an idiot!
here's my solution with map and multimap in C++

string frequencySort(string s) {
string ans = "";
map<char, int> m; // map to store char frequencies
multimap<int, char> mm; // multimap to store frequencies first

for(int i=0; i<s.size(); i++)
m[s[i]]++; // adding frequency of char

for(auto &it: m)
mm.insert({it.second, it.first}); // inserting freq first in multimap

multimap<int, char>::reverse_iterator it; // we have to traverse in reverse order
// as multimap is sorted in ascending order
for(it = mm.rbegin(); it != mm.rend(); it++){
for(int i=0; i<it->first; i++)
// we keep adding char the number of times it has occured
ans += it->second;
}
return ans;
}

[agileprogramming]

How can we solve it if we have to maintain the stability? I was thinking in terms of customized sort but couldn't implement it?

[spetsnaz_]

Hmm... That's why I was getting more Runtime due to using + in building string. Nice approach... My Code looks way complex than yours 😂

[jpakash]

Sir, how important is aptitude for placements.Do product companies ask aptitude ?

[ryan.aquino]

how about sorting it without using any sort helpers