# Minimum Deletions to Make String K-Special
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-deletions-to-make-string-k-special)
Canonical: https://scaleengineer.com/dsa/problems/minimum-deletions-to-make-string-k-special
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Hash Table, String
**Companies:** [DE Shaw](https://scaleengineer.com/companies/de-shaw)
---
## 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_**.

**Example 1:**

**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:**

**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:**

**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 <= 105`
* `0 <= k <= 105`
* `word` consists only of lowercase English letters.

# Approaches
## Brute-Force Iteration Over All Possible Frequencies
This approach involves calculating the initial frequencies of all characters. Then, it iterates through every possible value for the minimum frequency (`min_f`) in the final k-special string, from 0 up to the maximum frequency found in the original string. For each `min_f`, it calculates the total deletions required to make all character frequencies fall within the range `[min_f, min_f + k]`. The minimum number of deletions found across all tested `min_f` values is the answer.
**Time:** O(N + M * C), where N is the length of `word`, M is the maximum frequency of any character, and C is the alphabet size (26). Counting frequencies takes O(N). The nested loops take O(M * C). In the worst case, M can be up to N, leading to O(N*C). · **Space:** O(C), where C is the size of the alphabet (26). This is for storing the character frequencies.
**Pros:** Simple to understand and implement.; Correct for all valid inputs.
**Cons:** Can be inefficient if the maximum frequency of a character is very large, as the outer loop's complexity depends on it.
### Explanation
First, we compute the frequency of each of the 26 lowercase English letters in the input `word`. An array of size 26 can be used for this. We also find the maximum frequency `max_freq` among all characters. We initialize a variable `min_deletions` to a very large value (e.g., `word.length()`). We then loop through each possible lower bound `floor` from 0 to `max_freq`. Inside the loop, for a given `floor`, the target frequency range is `[floor, floor + k]`. We calculate the number of deletions needed for this range by iterating through the 26 character frequencies. For each frequency `f`, if it's below `floor`, we add `f` to the current deletions. If it's above `floor + k`, we add `f - (floor + k)`. After calculating the total deletions for the chosen `floor`, we update our overall minimum. After the loop finishes, `min_deletions` will hold the result.

```java
class Solution {
    public int minimumDeletions(String word, int k) {
        int[] freq = new int[26];
        int maxFreq = 0;
        for (char c : word.toCharArray()) {
            freq[c - 'a']++;
            maxFreq = Math.max(maxFreq, freq[c - 'a']);
        }

        int minDeletions = word.length();

        for (int floor = 0; floor <= maxFreq; floor++) {
            int currentDeletions = 0;
            int ceiling = floor + k;
            for (int f : freq) {
                if (f == 0) continue;
                if (f < floor) {
                    currentDeletions += f;
                } else if (f > ceiling) {
                    currentDeletions += f - ceiling;
                }
            }
            minDeletions = Math.min(minDeletions, currentDeletions);
        }

        return minDeletions;
    }
}
```
### Algorithm
- Create an integer array `freq` of size 26 to store character frequencies.
- Iterate through the input `word` to populate the `freq` array and find the maximum frequency `max_freq`.
- Initialize `min_deletions` to the total number of characters in the word.
- Loop a variable `floor` from 0 up to `max_freq`. This `floor` represents the potential minimum frequency in the final k-special string.
- Inside the loop, calculate the `current_deletions` required to make all character frequencies fit within the range `[floor, floor + k]`.
- For each character frequency `f` in the `freq` array:
  - If `f < floor`, add `f` to `current_deletions`.
  - If `f > floor + k`, add `f - (floor + k)` to `current_deletions`.
- After iterating through all character frequencies, update `min_deletions = min(min_deletions, current_deletions)`.
- After the loop over `floor` completes, return `min_deletions`.

## Iterating Over Unique Frequencies as Lower Bounds
This approach improves upon the brute-force method by observing that the optimal lower bound for the final frequency range must be related to the initial frequencies. Instead of checking every integer from 0 to `max_freq`, we only need to check values that correspond to the frequencies of characters present in the string. We can iterate through each unique non-zero frequency `f` as a potential lower bound `min_f`, calculate the deletions, and find the minimum. We also need to consider `min_f = 0`.
**Time:** O(N + C^2), where N is the length of `word` and C is the alphabet size (26). Counting frequencies is O(N). There are at most C unique frequencies. For each unique frequency, we iterate through all C frequencies, resulting in O(C^2) for the main logic. Since C is a small constant, this is effectively O(N). · **Space:** O(C), where C is the alphabet size (26). This is for storing frequencies and the set of unique frequencies.
**Pros:** Much more efficient than the brute-force approach.; Guaranteed to pass within time limits for the given constraints.
**Cons:** Involves a nested loop structure over the character set, which can be further optimized.
### Explanation
The core idea is that the cost function (number of deletions) only changes its form when the lower bound `floor` or upper bound `floor + k` crosses one of the existing frequency values. Therefore, we only need to test `floor` values that are equal to one of the initial frequencies. The algorithm first computes all character frequencies. Then, it gathers all unique non-zero frequencies into a set and adds 0 to it. It then iterates through this set of unique frequencies. For each unique frequency `u` considered as the `floor`, it calculates the total deletions required and updates the minimum deletions found so far. This significantly reduces the number of iterations compared to the brute-force approach.

```java
import java.util.*;

class Solution {
    public int minimumDeletions(String word, int k) {
        int[] freq = new int[26];
        for (char c : word.toCharArray()) {
            freq[c - 'a']++;
        }

        Set<Integer> uniqueFreqs = new HashSet<>();
        uniqueFreqs.add(0);
        for (int f : freq) {
            if (f > 0) {
                uniqueFreqs.add(f);
            }
        }

        int minDeletions = word.length();

        for (int floor : uniqueFreqs) {
            int currentDeletions = 0;
            int ceiling = floor + k;
            for (int f : freq) {
                if (f == 0) continue;
                if (f < floor) {
                    currentDeletions += f;
                } else if (f > ceiling) {
                    currentDeletions += f - ceiling;
                }
            }
            minDeletions = Math.min(minDeletions, currentDeletions);
        }

        return minDeletions;
    }
}
```
### Algorithm
- First, calculate the frequencies of all characters in the `word` and store them in an array `freq`.
- Create a `Set` to store all unique non-zero frequencies from the `freq` array. Add 0 to this set as well, as it's a valid lower bound for the final frequency range.
- Initialize `min_deletions` to `word.length()`.
- Iterate through each `floor` value in the set of unique frequencies.
- For each `floor`, calculate the `current_deletions` needed to bring all character frequencies into the range `[floor, floor + k]`.
  - Iterate through all 26 frequencies `f` in the `freq` array.
  - If `f < floor`, add `f` to `current_deletions`.
  - If `f > floor + k`, add `f - (floor + k)` to `current_deletions`.
- Update `min_deletions = min(min_deletions, current_deletions)`.
- Return `min_deletions`.

## Optimal Approach with Sorting and Prefix Sums
This is the most efficient approach. It builds upon the idea of checking only relevant lower bounds. By first sorting the character frequencies, we can calculate the number of deletions for each potential range much faster. We use prefix sums to quickly calculate the sum of frequencies that are too low. For frequencies that are too high, we can find them efficiently using binary search on the sorted frequency list and then use prefix sums to calculate the required deletions.
**Time:** O(N + C log C), where N is the length of `word` and C is the alphabet size. O(N) for frequency counting, O(C log C) for sorting, and O(C log C) for the main loop with binary search. This is the optimal time complexity. · **Space:** O(C), where C is the alphabet size (26). Space is used for the frequency list and the prefix sum array.
**Pros:** The most efficient algorithm with the best time complexity.; Scales very well with the problem constraints.
**Cons:** Slightly more complex to implement due to sorting, prefix sums, and binary search.
### Explanation
The key insight is that if we decide to keep a character with frequency `f`, to minimize deletions, we should make `f` the minimum frequency in our final set. This sets the target range to `[f, f+k]`. We can iterate through each of the original frequencies as this potential minimum. By sorting the frequencies first, we can efficiently calculate the costs. For each `freqs[i]` as the chosen minimum, all frequencies `freqs[0...i-1]` must be deleted (cost is `prefix_sum[i]`). For frequencies `freqs[j]` greater than `freqs[i] + k`, they must be reduced. We use binary search to find the block of such frequencies and prefix sums to calculate the deletion cost for them quickly. This avoids the O(C) inner loop of the previous approach.

```java
import java.util.*;

class Solution {
    public int minimumDeletions(String word, int k) {
        int[] freqArr = new int[26];
        for (char c : word.toCharArray()) {
            freqArr[c - 'a']++;
        }

        List<Integer> freqs = new ArrayList<>();
        for (int f : freqArr) {
            if (f > 0) {
                freqs.add(f);
            }
        }
        Collections.sort(freqs);

        if (freqs.isEmpty()) {
            return 0;
        }

        int n = freqs.size();
        int[] prefixSum = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + freqs.get(i);
        }

        int minDeletions = prefixSum[n]; // Cost to delete all characters
        
        for (int i = 0; i < n; i++) {
            int currentDeletions = prefixSum[i]; // Delete all freqs smaller than freqs.get(i)
            
            int ceiling = freqs.get(i) + k;
            
            int j = findUpperBound(freqs, ceiling);
            
            if (j < n) {
                int sumOfLarger = prefixSum[n] - prefixSum[j];
                int countOfLarger = n - j;
                currentDeletions += sumOfLarger - (countOfLarger * ceiling);
            }
            
            minDeletions = Math.min(minDeletions, currentDeletions);
        }

        return minDeletions;
    }

    private int findUpperBound(List<Integer> list, int target) {
        int low = 0, high = list.size();
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (list.get(mid) <= target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
}
```
### Algorithm
- Compute the frequencies of all characters and store the non-zero frequencies in a list `freqs`.
- Sort the `freqs` list in ascending order.
- Create a `prefix_sum` array for `freqs`, where `prefix_sum[i]` stores the sum of the first `i` frequencies.
- Initialize `min_deletions` with the cost of deleting all characters, which is the total sum of all frequencies (`prefix_sum[n]`).
- Iterate `i` from 0 to `n-1`, where `n` is the number of unique character frequencies. In each iteration, `freqs[i]` is considered the minimum frequency of a character we keep.
- For each `i`:
  - Calculate `deletions_lower`: the cost of deleting all characters with frequencies less than `freqs[i]`. This is `prefix_sum[i]`.
  - Define the target range as `[freqs[i], freqs[i] + k]`.
  - Calculate `deletions_upper`: the cost of reducing frequencies that are greater than `freqs[i] + k`. Find the first index `j` where `freqs[j] > freqs[i] + k` using binary search. The cost is `(sum of freqs from j to n-1) - (number of such freqs) * (freqs[i] + k)`. This can be computed in O(1) using the prefix sum array after finding `j`.
  - The total deletions for this case is `deletions_lower + deletions_upper`.
  - Update `min_deletions` with the minimum value found.
- Return `min_deletions`.

# Solutions
### Java

```java
class Solution {
private
  List<Integer> nums = new ArrayList<>();
public
  int minimumDeletions(String word, int k) {
    int[] freq = new int[26];
    int n = word.length();
    for (int i = 0; i < n; ++i) {
      ++freq[word.charAt(i) - 'a'];
    }
    for (int v : freq) {
      if (v > 0) {
        nums.add(v);
      }
    }
    int ans = n;
    for (int i = 0; i <= n; ++i) {
      ans = Math.min(ans, f(i, k));
    }
    return ans;
  }
private
  int f(int v, int k) {
    int ans = 0;
    for (int x : nums) {
      if (x < v) {
        ans += x;
      } else if (x > v + k) {
        ans += x - v - k;
      }
    }
    return ans;
  }
}

```

### Python

```python
class Solution:
    def minimumDeletions(self, word: str, k: int) -> int: def f(v: int) -> int: ans = 0 for x in nums: if x < v: ans += x elif x > v + k: ans += x - v - k return ans nums = Counter(word). values() return min(f(v) for v in range(len(word) + 1))

```

### CPP

```cpp
class Solution {
public:
  int minimumDeletions(string word, int k) {
    int freq[26]{};
    for (char &c : word) {
      ++freq[c - 'a'];
    }
    vector<int> nums;
    for (int v : freq) {
      if (v) {
        nums.push_back(v);
      }
    }
    int n = word.size();
    int ans = n;
    auto f = [&](int v) {
      int ans = 0;
      for (int x : nums) {
        if (x < v) {
          ans += x;
        } else if (x > v + k) {
          ans += x - v - k;
        }
      }
      return ans;
    };
    for (int i = 0; i <= n; ++i) {
      ans = min(ans, f(i));
    }
    return ans;
  }
};

```