# 451. Sort Characters By Frequency

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.
``````

``````class Solution {
public:
string frequencySort(string s) {
string res = "";
priority_queue<pair<int, char>> q;
unordered_map<char, int> m;
for (char c : s) ++m[c];
for (auto a : m) q.push({a.second, a.first});
while (!q.empty()) {
auto t = q.top(); q.pop();
res.append(t.first, t.second);
}
return res;
}
};
``````

``````class Solution {
public:
string frequencySort(string s) {
unordered_map<char, int> m;
for (char c : s) ++m[c];
sort(s.begin(), s.end(), [&](char& a, char& b){
return m[a] > m[b] || (m[a] == m[b] && a < b);
});
return s;
}
};
``````

``````class Solution {
public:
string frequencySort(string s) {
string res;
vector<string> v(s.size() + 1);
unordered_map<char, int> m;
for (char c : s) ++m[c];
for (auto &a : m) {
v[a.second].append(a.second, a.first);
}
for (int i = s.size(); i > 0; --i) {
if (!v[i].empty()) res.append(v[i]);
}
return res;
}
};
``````

Top K Frequent Words

First Unique Character in a String

https://leetcode.com/problems/sort-characters-by-frequency/description/

https://leetcode.com/problems/sort-characters-by-frequency/discuss/93404/c-on-solution-without-sort

https://leetcode.com/problems/sort-characters-by-frequency/discuss/93409/concise-c-solution-using-stl-sort

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation