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: Hash Table + Sorting
We use a hash table cnt to count the occurrences of each character in the string s. Then, we sort the key-value pairs in cnt in descending order by the number of occurrences. Finally, we concatenate the characters according to the sorted order.
The time complexity is O(n + k × log k), and the space complexity is O(n + k), where n is the length of the string s, and k is the number of distinct characters.
PythonJavaC++GoTypeScriptRustPHP
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]))(code-box)
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();
}
}(code-box)
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;
}
};(code-box)
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)
}(code-box)
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('');
}(code-box)
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()
}
}(code-box)
class Solution {
/**
* @param String $s
* @return String
*/
function frequencySort($s) {
$cnt = array_count_values(str_split($s));
$cs = array_keys($cnt);
usort($cs, function ($a, $b) use ($cnt) {
return $cnt[$b] <=> $cnt[$a];
});
$ans = '';
foreach ($cs as $c) {
$ans .= str_repeat($c, $cnt[$c]);
}
return $ans;
}
}(code-box)
