# Minimum Deletions for At Most K Distinct Characters
**Difficulty:** EASY
[External](https://leetcode.com/problems/minimum-deletions-for-at-most-k-distinct-characters)
Canonical: https://scaleengineer.com/dsa/problems/minimum-deletions-for-at-most-k-distinct-characters
**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
---
## Problem
You are given a string `s` consisting of lowercase English letters, and an integer `k`.

Your task is to delete some (possibly none) of the characters in the string so that the number of **distinct** characters in the resulting string is **at most** `k`.

Return the **minimum** number of deletions required to achieve this.

**Example 1:**

**Input:** s = "abc", k = 2

**Output:** 1

**Explanation:**

* `s` has three distinct characters: `'a'`, `'b'` and `'c'`, each with a frequency of 1.
* Since we can have at most `k = 2` distinct characters, remove all occurrences of any one character from the string.
* For example, removing all occurrences of `'c'` results in at most `k` distinct characters. Thus, the answer is 1.

**Example 2:**

**Input:** s = "aabb", k = 2

**Output:** 0

**Explanation:**

* `s` has two distinct characters (`'a'` and `'b'`) with frequencies of 2 and 2, respectively.
* Since we can have at most `k = 2` distinct characters, no deletions are required. Thus, the answer is 0.

**Example 3:**

**Input:** s = "yyyzz", k = 1

**Output:** 2

**Explanation:**

* `s` has two distinct characters (`'y'` and `'z'`) with frequencies of 3 and 2, respectively.
* Since we can have at most `k = 1` distinct character, remove all occurrences of any one character from the string.
* Removing all `'z'` results in at most `k` distinct characters. Thus, the answer is 2.

**Constraints:**

* `1 <= s.length <= 16`
* `1 <= k <= 16`
* `s` consists only of lowercase English letters.

# Approaches
## Brute-force by Checking All Character Subsets
This approach considers all possible scenarios. The goal is to select exactly `k` distinct characters to keep in the final string. All other characters must be deleted. We can systematically generate every possible subset of `k` distinct characters from the set of unique characters present in the original string. For each subset, we calculate the total number of deletions required, which is the sum of frequencies of all characters *not* in our chosen subset. By comparing the deletion counts for all possible subsets, we can find the minimum one.
**Time:** O(N + C(D, k) * k), where N is the string length, D is the number of distinct characters. `C(D, k)` is the number of combinations. `O(N)` to build the frequency map. Then we generate `C(D, k)` combinations and for each, we sum `k` frequencies. Given the constraints, this is feasible. · **Space:** O(D + k), where D is the number of distinct characters. We use space for the frequency map, the list of distinct characters, and the recursion stack. Since D is at most 26, this is effectively O(1).
**Pros:** It's a conceptually straightforward, exhaustive search that guarantees the optimal solution.
**Cons:** Can be slow if the number of distinct characters `d` and `k` are large (e.g., `d=26, k=13`).; More complex to implement compared to a greedy approach due to the need for a combination generation algorithm (like backtracking).
### Explanation
The algorithm proceeds as follows:
1.  First, we determine the frequency of each character in the input string `s`. A hash map or an array of size 26 can be used for this. We also collect the set of unique characters present in the string.
2.  Let the number of distinct characters be `d`. If `d` is less than or equal to `k`, it means we already satisfy the condition, so no deletions are needed. We return 0.
3.  If `d > k`, we must choose which `k` characters to keep. We generate all combinations of size `k` from the set of `d` unique characters.
4.  For each combination (a subset of `k` characters to keep), we calculate the number of deletions. This is done by summing the frequencies of all characters that are *not* in the current combination.
5.  We maintain a variable to keep track of the minimum number of deletions found so far across all combinations.
6.  After checking all combinations, this variable will hold the minimum possible deletions, which is our answer.

This method is exhaustive and guarantees finding the correct answer, but its performance depends on the number of combinations. Given the small constraints (`s.length <= 16`, `k <= 16`, and at most 26 distinct characters), this approach is feasible.

```java
import java.util.*;

class Solution {
    int minDeletions = Integer.MAX_VALUE;

    public int minDeletions(String s, int k) {
        Map<Character, Integer> freqMap = new HashMap<>();
        for (char c : s.toCharArray()) {
            freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);
        }

        List<Character> distinctChars = new ArrayList<>(freqMap.keySet());
        int d = distinctChars.size();

        if (d <= k) {
            return 0;
        }

        // Generate all combinations of k characters to keep
        findMinDeletions(0, new ArrayList<>(), distinctChars, k, freqMap, s.length());
        
        return minDeletions;
    }

    private void findMinDeletions(int start, List<Character> currentCombination, List<Character> distinctChars, int k, Map<Character, Integer> freqMap, int totalLength) {
        if (currentCombination.size() == k) {
            int charsToKeep = 0;
            for (char c : currentCombination) {
                charsToKeep += freqMap.get(c);
            }
            minDeletions = Math.min(minDeletions, totalLength - charsToKeep);
            return;
        }

        if (start == distinctChars.size()) {
            return;
        }

        for (int i = start; i < distinctChars.size(); i++) {
            // Include character at index i
            currentCombination.add(distinctChars.get(i));
            findMinDeletions(i + 1, currentCombination, distinctChars, k, freqMap, totalLength);
            // Backtrack
            currentCombination.remove(currentCombination.size() - 1);
        }
    }
}
```
### Algorithm
*   Create a frequency map to count occurrences of each character in `s`.
*   Create a list of unique characters present in `s`.
*   If the number of unique characters is at most `k`, return 0.
*   Initialize `minDeletions` to a very large value (e.g., `s.length()`).
*   Generate all subsets of size `k` from the list of unique characters. This can be done using a recursive backtracking function.
*   For each subset of `k` characters:
    *   Calculate the total number of characters to keep by summing their frequencies from the map.
    *   The number of deletions for this subset is `s.length() - totalToKeep`.
    *   Update `minDeletions = min(minDeletions, currentDeletions)`.
*   Return `minDeletions`.

## Greedy Approach using Frequency Sorting
A more efficient approach is based on a greedy strategy. To minimize the number of deletions, we should maximize the number of characters we keep. The problem states we can keep at most `k` distinct characters. To maximize the kept characters, it's always optimal to keep the `k` characters that appear most frequently in the original string. Any other characters must be completely removed.

This greedy choice works because by removing the least frequent characters, we eliminate a distinct character class while incurring the minimum possible number of deletions for that elimination.
**Time:** O(N + D log D), where N is the string length and D is the number of distinct characters. Since D is at most 26, `D log D` is a constant factor. Thus, the complexity is effectively O(N). · **Space:** O(D), where D is the number of distinct characters. We use an array of size 26 and a list of size D. Since D <= 26, the space complexity is constant, O(1).
**Pros:** Highly efficient, with a linear time complexity with respect to the input string length.; Simple to understand and implement.; The greedy choice is provably optimal.
**Cons:** The correctness of the greedy approach might not be immediately obvious without reasoning about why keeping the most frequent characters is always the best strategy.
### Explanation
The algorithm is as follows:
1.  First, calculate the frequency of each character in the input string `s`. An array of size 26 is sufficient since the string contains only lowercase English letters.
2.  From the frequency map, extract the frequencies of only the characters that are present in the string (i.e., frequencies greater than 0). Store these in a list.
3.  Let `d` be the number of distinct characters, which is the size of this list of frequencies.
4.  If `d <= k`, we already meet the condition, so no deletions are required. The answer is 0.
5.  If `d > k`, we need to eliminate `d - k` distinct characters. To minimize deletions, we should eliminate the `d - k` characters with the lowest frequencies.
6.  Sort the list of frequencies in ascending order.
7.  The minimum number of deletions will be the sum of the first `d - k` smallest frequencies in the sorted list. These correspond to the characters we choose to completely remove.
8.  Sum these `d - k` frequencies and return the result.

```java
import java.util.*;

class Solution {
    public int minDeletions(String s, int k) {
        // Step 1: Calculate character frequencies.
        int[] freq = new int[26];
        for (char c : s.toCharArray()) {
            freq[c - 'a']++;
        }

        // Step 2: Collect non-zero frequencies.
        List<Integer> frequencyList = new ArrayList<>();
        for (int count : freq) {
            if (count > 0) {
                frequencyList.add(count);
            }
        }

        // Step 3: If distinct characters are already at most k, no deletions needed.
        int distinctCount = frequencyList.size();
        if (distinctCount <= k) {
            return 0;
        }

        // Step 4: Sort frequencies to find the smallest ones.
        Collections.sort(frequencyList);

        // Step 5: Sum the frequencies of the characters to be deleted.
        // We need to remove `distinctCount - k` characters.
        int deletions = 0;
        int charsToRemove = distinctCount - k;
        for (int i = 0; i < charsToRemove; i++) {
            deletions += frequencyList.get(i);
        }

        return deletions;
    }
}
```
### Algorithm
*   Create an integer array `freq` of size 26, initialized to zeros.
*   Iterate through the input string `s` and increment `freq[c - 'a']` for each character `c`.
*   Create a list `frequencyList` to store the non-zero frequencies from the `freq` array.
*   If `frequencyList.size() <= k`, return 0.
*   Sort `frequencyList` in ascending order.
*   Initialize `deletions = 0`.
*   Iterate from `i = 0` to `frequencyList.size() - k - 1`. In each iteration, add `frequencyList.get(i)` to `deletions`.
*   Return `deletions`.

# Solutions
### Java

```java
class Solution {
public
  int minDeletion(String s, int k) {
    int[] cnt = new int[26];
    for (char c : s.toCharArray()) {
      ++cnt[c - 'a'];
    }
    Arrays.sort(cnt);
    int ans = 0;
    for (int i = 0; i + k < 26; ++i) {
      ans += cnt[i];
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minDeletion(string s, int k) {
    vector<int> cnt(26);
    for (char c : s) {
      ++cnt[c - 'a'];
    }
    ranges ::sort(cnt);
    int ans = 0;
    for (int i = 0; i + k < 26; ++i) {
      ans += cnt[i];
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minDeletion(
        self, s: str, k: int) -> int: return sum(sorted(Counter(s). values())[: - k])

```