Minimum deletions for at most k distinct characters

Hash Table String Greedy Sorting Counting

72.9% acceptance

Feb 25, 2026

Given a string s and integer k, delete minimum characters so that distinct character count <= k. Return the minimum number of deletions.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_deletion(s: String, k: i32) -> i32 {
    let k = k as usize;
    let mut freq = [0i32; 26];
    for b in s.bytes() {
      freq[(b - b'a') as usize] += 1;
    }
    let mut counts: Vec<i32> = freq.iter().filter(|&&f| f > 0).copied().collect();
    let distinct = counts.len();
    if distinct <= k {
      return 0;
    }
    // Remove (distinct - k) character types, minimizing total deletions = sum of removed freq
    counts.sort_unstable();
    // Remove the (distinct-k) smallest frequency types
    counts[..distinct - k].iter().sum()
  }
}