Problem

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.

Here, freq(x) denotes the frequency of the character x in word, and |y| denotes the absolute value of y.

Return the minimum number of characters you need to delete to make word k-special.

Examples

Example 1

1
2
3

Input: word = "aabcaba", k = 0
Output: 3
Explanation: We can make word 0-special by deleting 2 occurrences of "a" and 1 occurrence of "c". Therefore, word becomes equal to "baba" where freq('a') == freq('b') == 2.

Example 2

1
2
3

Input: word = "dabdcbdcdcd", k = 2
Output: 2
Explanation: We can make word 2-special by deleting 1 occurrence of "a" and 1 occurrence of "d". Therefore, word becomes equal to "bdcbdcdcd" where freq('b') == 2, freq('c') == 3, and freq('d') == 4.

Example 3

1
2
3

Input: word = "aaabaaa", k = 2
Output: 1
Explanation: We can make word 2-special by deleting 1 occurrence of "b". Therefore, word becomes equal to "aaaaaa" where each letter's frequency is now uniformly 6.

Constraints

  • 1 <= word.length <= 10^5
  • 0 <= k <= 10^5
  • word consists only of lowercase English letters.

Solution

Method 1 – Greedy Frequency Balancing

Intuition

To make the string k-special, the difference between the maximum and minimum frequency of any character must not exceed k. By deleting characters, we can reduce the frequencies to fit this constraint. The optimal way is to try all possible target frequencies and calculate the minimum deletions needed for each, then pick the smallest.

Approach

  1. Count the frequency of each character in the string.
  2. Sort the frequencies.
  3. For each possible target frequency f (from 0 up to the maximum frequency), calculate the total deletions needed:
  • For characters with frequency less than f, delete all occurrences.
  • For characters with frequency greater than f + k, delete enough occurrences to reduce their frequency to f + k.
  • For characters with frequency in [f, f + k], keep them as is.
  1. Return the minimum deletions found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
   int minimumDeletions(string word, int k) {
      vector<int> freq(26, 0);
      for (char c : word) freq[c - 'a']++;
      vector<int> f;
      for (int x : freq) if (x) f.push_back(x);
      sort(f.begin(), f.end());
      int ans = word.size();
      for (int i = 0; i < f.size(); ++i) {
        int base = f[i], del = 0;
        for (int j = 0; j < f.size(); ++j) {
           if (f[j] < base) del += f[j];
           else if (f[j] > base + k) del += f[j] - (base + k);
        }
        ans = min(ans, del);
      }
      return ans;
   }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

func minimumDeletions(word string, k int) int {
   freq := make([]int, 26)
   for _, c := range word {
      freq[c-'a']++
   }
   f := []int{}
   for _, x := range freq {
      if x > 0 {
        f = append(f, x)
      }
   }
   sort.Ints(f)
   ans := len(word)
   for i := 0; i < len(f); i++ {
      base, del := f[i], 0
      for _, v := range f {
        if v < base {
           del += v
        } else if v > base+k {
           del += v - (base + k)
        }
      }
      if del < ans {
        ans = del
      }
   }
   return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
   public int minimumDeletions(String word, int k) {
      int[] freq = new int[26];
      for (char c : word.toCharArray()) freq[c - 'a']++;
      List<Integer> f = new ArrayList<>();
      for (int x : freq) if (x > 0) f.add(x);
      Collections.sort(f);
      int ans = word.length();
      for (int i = 0; i < f.size(); ++i) {
        int base = f.get(i), del = 0;
        for (int v : f) {
           if (v < base) del += v;
           else if (v > base + k) del += v - (base + k);
        }
        ans = Math.min(ans, del);
      }
      return ans;
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
   fun minimumDeletions(word: String, k: Int): Int {
      val freq = IntArray(26)
      for (c in word) freq[c - 'a']++
      val f = freq.filter { it > 0 }.sorted()
      var ans = word.length
      for (i in f.indices) {
        val base = f[i]
        var del = 0
        for (v in f) {
           if (v < base) del += v
           else if (v > base + k) del += v - (base + k)
        }
        ans = minOf(ans, del)
      }
      return ans
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
   def minimumDeletions(self, word: str, k: int) -> int:
      freq: list[int] = [0] * 26
      for c in word:
        freq[ord(c) - ord('a')] += 1
      f: list[int] = [x for x in freq if x > 0]
      f.sort()
      ans: int = len(word)
      for i in range(len(f)):
        base = f[i]
        del_cnt = 0
        for v in f:
           if v < base:
              del_cnt += v
           elif v > base + k:
              del_cnt += v - (base + k)
        ans = min(ans, del_cnt)
      return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

impl Solution {
   pub fn minimum_deletions(word: String, k: i32) -> i32 {
      let mut freq = [0; 26];
      for c in word.chars() {
        freq[(c as u8 - b'a') as usize] += 1;
      }
      let mut f: Vec<i32> = freq.iter().filter(|&&x| x > 0).map(|&x| x).collect();
      f.sort();
      let mut ans = word.len() as i32;
      for &base in &f {
        let mut del = 0;
        for &v in &f {
           if v < base {
              del += v;
           } else if v > base + k {
              del += v - (base + k);
           }
        }
        ans = ans.min(del);
      }
      ans
   }
}

Complexity

  • ⏰ Time complexity: O(26^2) (since there are at most 26 unique letters, so the double loop is constant time)
  • 🧺 Space complexity: O(26) (for frequency array)