Description#
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 * 105s consists of uppercase and lowercase English letters and digits.
Solutions#
Solution 1#
1
2
3
4
| class Solution:
def frequencySort(self, s: str) -> str:
cnt = Counter(s)
return ''.join(c * v for c, v in sorted(cnt.items(), key=lambda x: -x[1]))
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public String frequencySort(String s) {
Map<Character, Integer> cnt = new HashMap<>(52);
for (int i = 0; i < s.length(); ++i) {
cnt.merge(s.charAt(i), 1, Integer::sum);
}
List<Character> cs = new ArrayList<>(cnt.keySet());
cs.sort((a, b) -> cnt.get(b) - cnt.get(a));
StringBuilder ans = new StringBuilder();
for (char c : cs) {
for (int v = cnt.get(c); v > 0; --v) {
ans.append(c);
}
}
return ans.toString();
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
string frequencySort(string s) {
unordered_map<char, int> cnt;
for (char& c : s) {
++cnt[c];
}
vector<char> cs;
for (auto& [c, _] : cnt) {
cs.push_back(c);
}
sort(cs.begin(), cs.end(), [&](char& a, char& b) {
return cnt[a] > cnt[b];
});
string ans;
for (char& c : cs) {
ans += string(cnt[c], c);
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| func frequencySort(s string) string {
cnt := map[byte]int{}
for i := range s {
cnt[s[i]]++
}
cs := make([]byte, 0, len(s))
for c := range cnt {
cs = append(cs, c)
}
sort.Slice(cs, func(i, j int) bool { return cnt[cs[i]] > cnt[cs[j]] })
ans := make([]byte, 0, len(s))
for _, c := range cs {
ans = append(ans, bytes.Repeat([]byte{c}, cnt[c])...)
}
return string(ans)
}
|
1
2
3
4
5
6
7
8
9
10
11
12
| function frequencySort(s: string): string {
const cnt: Map<string, number> = new Map();
for (const c of s) {
cnt.set(c, (cnt.get(c) || 0) + 1);
}
const cs = Array.from(cnt.keys()).sort((a, b) => cnt.get(b)! - cnt.get(a)!);
const ans: string[] = [];
for (const c of cs) {
ans.push(c.repeat(cnt.get(c)!));
}
return ans.join('');
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| use std::collections::HashMap;
impl Solution {
pub fn frequency_sort(s: String) -> String {
let mut cnt = HashMap::new();
for c in s.chars() {
cnt.insert(c, cnt.get(&c).unwrap_or(&0) + 1);
}
let mut cs = cnt.into_iter().collect::<Vec<(char, i32)>>();
cs.sort_unstable_by(|(_, a), (_, b)| b.cmp(&a));
cs.into_iter()
.map(|(c, v)| vec![c; v as usize].into_iter().collect::<String>())
.collect()
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| 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;
}
}
|
