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.
class Solution {
public:
//桶排序。将相同长度的子串放到同一个桶中，最后利用桶排序
string frequencySort(string s) {
//防止s="aaa" 插入 b[3] = "aaa";
vector<string> bucket(s.size()+1,"");
map<char,int> m;
string res;
for(int i=0;i<s.size();i++){
m[s[i]]++;
}
for(auto sub:m){
int n = sub.second;
int c = sub.first;
//长度为n的子串都放到bucket[n]
bucket[n].append(string(n,c));
}
//最后利用桶排序，倒序遍历桶即可
for(int i=bucket.size()-1;i>=0;i--){
res.append(bucket[i]);
}
return res;
}
};