LeetCode Entry

451. Sort Characters By Frequency

07.02.2024 medium 2024 kotlin rust

Sort string by char's frequencies.

451. Sort Characters By Frequency medium blog post substack youtube image.png

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 string

  • Space 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()
  }