# Sort Characters By Frequency

Nov 11, 2019

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.


1. 计数算频率，用unordered_map就搞定了
2. 按频率排序，先把unoredred_map转成vector，然后再sort
3. 生成字符串。

string frequencySort(string s) {
unordered_map<char, int> cmap;
for(int i = 0;i < s.size(); i++) cmap[s[i]]++;
vector<pair<char, int>> pvec(cmap.begin(), cmap.end());
sort(pvec.begin(), pvec.end(), [](const pair<char, int> &p1, const pair<char, int> &p2) {
return p1.second > p2.second;
});

string res;
for(auto it = pvec.begin(); it != pvec.end(); ++it) {
res += string(it->second, it->first);
}
return res;
}


string frequencySort(string s) {
vector<pair<char, int> > pvec(256);
for(int i = 0;i < 256; i++) pvec[i] = make_pair(i, 0);
for(int i = 0;i < s.size(); i++) {
pvec[s[i]].second++;
}

string res;
for(auto it = pvec.begin(); it != pvec.end() && it->second; ++it) {
res += string(it->second, it->first);
}
return res;
}

LeetCodeLeetCode

Replace Words

Longest String Chain