Minimum deletions to make string k special

Hash Table String Greedy Sorting Counting

67.2% acceptance

Feb 25, 2026

679

You are given a string word and an integer k. We consider word to be k-special if |freq(word[i]) - freq(word[j])| <= k for all indices i and j in the string. Return the minimum number of characters you need to delete to make word k-special.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_deletions(word: String, k: i32) -> i32 {
    let mut freq = [0i32; 26];
    for b in word.bytes() { freq[(b - b'a') as usize] += 1; }
    let mut freqs: Vec<i32> = freq.iter().filter(|&&f| f > 0).cloned().collect();
    freqs.sort();
    let m = freqs.len();
    let mut ans = i32::MAX;
    // Try each frequency as the minimum frequency (after deletions)
    for i in 0..m {
      let min_f = freqs[i];
      let max_f = min_f + k;
      // Delete all chars with freq < min_f (delete them entirely)
      // For chars with freq > max_f, reduce to max_f
      let mut cost = 0i32;
      for j in 0..i { cost += freqs[j]; } // delete all
      for j in i..m {
        if freqs[j] > max_f { cost += freqs[j] - max_f; }
      }
      ans = ans.min(cost);
    }
    // Also try setting min to 0 (delete some entirely)
    ans.min({
      let mut cost = 0i32;
      for &f in &freqs { if f > k { cost += f - k; } }
      cost
    })
  }
}