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 * 105sconsists of uppercase and lowercase English letters and digits.
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)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<>();
}
buckets[freq].add(c);
}
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();
}
}Simulation with structure sorting.
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])
.map(([k, v]) => k.padStart(v, k))
.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()
}
}