##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/451.html

# 451. Sort Characters By Frequency (Medium)

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.


Related Topics:
Hash Table, Heap

Similar Questions:

## Solution 1.

• class Solution {
public String frequencySort(String s) {
Map<Character, Integer> map = new HashMap<Character, Integer>();
char[] array = s.toCharArray();
for (char c : array) {
int count = map.getOrDefault(c, 0);
count++;
map.put(c, count);
}
List<CharacterCount> list = new ArrayList<CharacterCount>();
Set<Character> keySet = map.keySet();
for (char c : keySet) {
int count = map.getOrDefault(c, 0);
}
Collections.sort(list);
StringBuffer sortedSB = new StringBuffer();
for (CharacterCount characterCount : list) {
char character = characterCount.character;
int count = characterCount.count;
for (int i = 0; i < count; i++)
sortedSB.append(character);
}
return sortedSB.toString();
}
}

class CharacterCount implements Comparable<CharacterCount> {
char character;
int count;

public CharacterCount(char character, int count) {
this.character = character;
this.count = count;
}

public int compareTo(CharacterCount characterCount2) {
return characterCount2.count - this.count;
}
}

############

class Solution {
public String frequencySort(String s) {
Map<Character, Integer> counter = new HashMap<>();
for (char c : s.toCharArray()) {
counter.put(c, counter.getOrDefault(c, 0) + 1);
}
List<Character>[] buckets = new List[s.length() + 1];
for (Map.Entry<Character, Integer> entry : counter.entrySet()) {
char c = entry.getKey();
int freq = entry.getValue();
if (buckets[freq] == null) {
buckets[freq] = new ArrayList<>();
}
}
StringBuilder sb = new StringBuilder();
for (int i = s.length(); i >= 0; --i) {
if (buckets[i] != null) {
for (char c : buckets[i]) {
for (int j = 0; j < i; ++j) {
sb.append(c);
}
}
}
}
return sb.toString();
}
}

• // OJ: https://leetcode.com/problems/sort-characters-by-frequency/
// Time: O(NlogN)
// Space: O(C)
class Solution {
public:
string frequencySort(string s) {
int cnt[256] = {};
for (char c : s) cnt[c]++;
sort(s.begin(), s.end(), [&](char a, char b) {
return cnt[a] == cnt[b] ? a > b : cnt[a] > cnt[b];
});
return s;
}
};

• class Solution:
def frequencySort(self, s: str) -> str:
counter = Counter(s)
buckets = defaultdict(list)
for c, freq in counter.items():
buckets[freq].append(c)
res = []
for i in range(len(s), -1, -1):
if buckets[i]:
for c in buckets[i]:
res.append(c * i)
return ''.join(res)

############

from collections import Counter

class Solution(object):
def frequencySort(self, s):
"""
:type s: str
:rtype: str
"""
d = Counter(s)
buf = {}
for k, v in d.items():
buf[v] = buf.get(v, "") + k * v
ans = ""
for i in reversed(range(0, len(s))):
ans += buf.get(i, "")
return ans


• type pair struct {
b   byte
cnt int
}

func frequencySort(s string) string {
freq := make(map[byte]int)
for _, r := range s {
freq[byte(r)]++
}
a := make([]pair, 0)
for k, v := range freq {
a = append(a, pair{b: k, cnt: v})
}
sort.Slice(a, func(i, j int) bool { return a[i].cnt > a[j].cnt })
var sb strings.Builder
for _, p := range a {
sb.Write(bytes.Repeat([]byte{p.b}, p.cnt))
}
return sb.String()
}


• function frequencySort(s: string): string {
const map = new Map<string, number>();
for (const c of s) {
map.set(c, (map.get(c) ?? 0) + 1);
}
return [...map.entries()]
.sort((a, b) => b[1] - a[1])
.join('');
}


• use std::collections::HashMap;
impl Solution {
pub fn frequency_sort(s: String) -> String {
let mut map = HashMap::new();
for c in s.chars() {
map.insert(c, map.get(&c).unwrap_or(&0) + 1);
}
let mut arr = map.into_iter().collect::<Vec<(char, i32)>>();
arr.sort_unstable_by(|(_, a), (_, b)| b.cmp(&a));
arr.into_iter()
.map(|(c, v)| vec![c; v as usize].into_iter().collect::<String>())
.collect()
}
}


•  class Solution {
/**
* @param String $s * @return String */ function frequencySort($s) {
for ($i = 0;$i < strlen($s);$i++) {
$hashtable[$s[$i]] += 1; } arsort($hashtable);
$keys = array_keys($hashtable);
for ($j = 0;$j < count($keys);$j++) {
$rs =$rs.str_repeat($keys[$j], $hashtable[$keys[$j]]); } return$rs;
}
};