07.02.2024
451. Sort Characters By Frequency medium
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/498
Problem TLDR
Sort string by char’s frequencies.
Intuition
The optimal solution would be to sort [128]
size array of frequencies, then build a string in O(n). There are some other ways, however…
Approach
Let’s explore the shortest versions of code by using the API:
Kotlin: groupBy, sortedBy, flatMap, joinToString
Rust: vec![], sort_unstable_by_key, just sorting the whole string takes 3ms
Complexity
Time complexity:
O(n), or O(nlog(n)) for sorting the whole stringSpace complexity:
O(n)
Code
fun frequencySort(s: String) = s
.groupBy { it }.values
.sortedBy { -it.size }
.flatMap { it }
.joinToString("")
pub fn frequency_sort(s: String) -> String {
let mut f = vec![0; 128];
for b in s.bytes() { f[b as usize] += 1 }
let mut cs: Vec<_> = s.chars().collect();
cs.sort_unstable_by_key(|&c| (-f[c as usize], c));
cs.iter().collect()
}