## Algorithm

Problem Name: 451. Sort Characters By Frequency

Given a string `s`, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string.

Return the sorted string. If there are multiple answers, return any of them.

Example 1:

```Input: s = "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: s = "cccaaa"
Output: "aaaccc"
Explanation: Both 'c' and 'a' appear three times, so both "cccaaa" and "aaaccc" are valid answers.
Note that "cacaca" is incorrect, as the same characters must be together.
```

Example 3:

```Input: s = "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.
```

Constraints:

• `1 <= s.length <= 5 * 105`
• `s` consists of uppercase and lowercase English letters and digits.

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
string frequencySort(string s) {
string res = "";
unordered_map < char, int>m;
for(auto c: s) m[c]++;
auto comp = [](pair < int, char>& a, pair<int, char>& b){ return a.first < b.first; };
priority_queue < pair<int, char>, vector<pair<int, char>>, decltype(comp)>pq(comp);
for(auto x: m) pq.push({x.second, x.first});
while(!pq.empty()){
auto p = pq.top();
pq.pop();
while(p.first--) res += p.second;
}
return res;
}
};
``````
Copy The Code &

Input

cmd
s = "tree"

Output

cmd
"eert"

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {

private static final String ALL_LETTERS =
"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

public String frequencySort(String s) {
Map < Character, Integer> map = new HashMap<>();
int maxFrequency = 0;
for (char c : s.toCharArray()) {
map.put(c, map.getOrDefault(c, 0) + 1);
maxFrequency = Math.max(maxFrequency, map.get(c));
}
List < Character>[] frequencyToChar = new List[maxFrequency + 1];
for (char c : map.keySet()) {
if (frequencyToChar[map.get(c)] == null) {
frequencyToChar[map.get(c)] = new ArrayList<>();
}
}
StringBuilder sb = new StringBuilder();
for (int i = maxFrequency; i > 0; i--) {
List < Character> characters = frequencyToChar[i] == null ?
new ArrayList<>() : frequencyToChar[i];
for (char c : characters) {
for (int j = 0; j  <  i; j++) {
sb.append(c);
}
}
}
return sb.toString();
}
}
``````
Copy The Code &

Input

cmd
s = "tree"

Output

cmd
"eert"

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const frequencySort = function(s) {
const charMap = {};
for (let i = 0; i  <  s.length; i++) {
const index = s.charAt(i);
charMap[index] = (charMap[index] || 0) + 1;
}
return Object.entries(charMap)
.sort((a, b) => {
return b[1] - a[1];
})
.map(x => {
return x[0].repeat(x[1]);
})
.join("");
};
``````
Copy The Code &

Input

cmd
s = "cccaaa"

Output

cmd
"aaaccc"

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def frequencySort(self, s: str) -> str:
cnt = collections.Counter(s)
res = ''
for k, v in sorted(cnt.items(), key = lambda x: -cnt[x[0]]):
res += k * v
return res
``````
Copy The Code &

Input

cmd
s = "cccaaa"

Output

cmd
"aaaccc"

### #5 Code Example with C# Programming

```Code - C# Programming```

``````
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace LeetCode
{
public class _0451_SortCharactersByFrequency
{
public string FrequencySort(string s)
{
if (string.IsNullOrWhiteSpace(s)) return s;

var counts = new Dictionary < char, int>();
foreach (var ch in s)
{
if (!counts.ContainsKey(ch))
else
counts[ch]++;
}

var maxCount = counts.Values.Max();
var buckets = new List < IList());
foreach (var ch in counts.Keys)

var sb = new StringBuilder();
for (int i = maxCount; i >= 1; i--)
foreach (var ch in buckets[i])
sb.Append(ch, i);

return sb.ToString();
}
}
}
``````
Copy The Code &

Input

cmd
s = "Aabb"

Output

cmd
"bbAa"