• Time:O(n)
• Space:O(n)

## C++

``````class Solution {
public:
string frequencySort(string s) {
const int n = s.length();
string ans;
vector<int> count(128);
// bucket[i] := stores chars that appear i times in s
vector<vector<char>> bucket(n + 1);

for (const char c : s)
++count[c];

for (int i = 0; i < 128; ++i) {
const int freq = count[i];
if (freq > 0)
bucket[freq].push_back((char)i);
}

for (int freq = n; freq > 0; --freq)
for (const char c : bucket[freq])
ans += string(freq, c);

return ans;
}
};
``````

## JAVA

``````class Solution {
public String frequencySort(String s) {
final int n = s.length();
StringBuilder sb = new StringBuilder();
int[] count = new int[128];
// bucket[i] := stores chars that appear i times in s
List<Character>[] bucket = new List[n + 1];

for (final char c : s.toCharArray())
++count[c];

for (int i = 0; i < 128; ++i) {
final int freq = count[i];
if (freq > 0) {
if (bucket[freq] == null)
bucket[freq] = new ArrayList<>();
}
}

for (int freq = n; freq > 0; --freq)
if (bucket[freq] != null)
for (final char c : bucket[freq])
for (int i = 0; i < freq; ++i)
sb.append(c);

return sb.toString();
}
}
``````

## Python

``````class Solution:
def frequencySort(self, s: str) -> str:
ans = []
bucket = [[] for _ in range(len(s) + 1)]

for c, freq in Counter(s).items():
bucket[freq].append(c)

for freq in reversed(range(len(bucket))):
for c in bucket[freq]:
ans.append(c * freq)

return ''.join(ans)
``````