Minimum Deletions for At Most K Distinct Characters

• 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.

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.

1import java.util.*;2 3class Solution {4    int minDeletions = Integer.MAX_VALUE;5 6    public int minDeletions(String s, int k) {7        Map<Character, Integer> freqMap = new HashMap<>();8        for (char c : s.toCharArray()) {9            freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);10        }11 12        List<Character> distinctChars = new ArrayList<>(freqMap.keySet());13        int d = distinctChars.size();14 15        if (d <= k) {16            return 0;17        }18 19        // Generate all combinations of k characters to keep20        findMinDeletions(0, new ArrayList<>(), distinctChars, k, freqMap, s.length());21        22        return minDeletions;23    }24 25    private void findMinDeletions(int start, List<Character> currentCombination, List<Character> distinctChars, int k, Map<Character, Integer> freqMap, int totalLength) {26        if (currentCombination.size() == k) {27            int charsToKeep = 0;28            for (char c : currentCombination) {29                charsToKeep += freqMap.get(c);30            }31            minDeletions = Math.min(minDeletions, totalLength - charsToKeep);32            return;33        }34 35        if (start == distinctChars.size()) {36            return;37        }38 39        for (int i = start; i < distinctChars.size(); i++) {40            // Include character at index i41            currentCombination.add(distinctChars.get(i));42            findMinDeletions(i + 1, currentCombination, distinctChars, k, freqMap, totalLength);43            // Backtrack44            currentCombination.remove(currentCombination.size() - 1);45        }46    }47}

• 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.

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.

1import java.util.*;2 3class Solution {4    public int minDeletions(String s, int k) {5        // Step 1: Calculate character frequencies.6        int[] freq = new int[26];7        for (char c : s.toCharArray()) {8            freq[c - 'a']++;9        }10 11        // Step 2: Collect non-zero frequencies.12        List<Integer> frequencyList = new ArrayList<>();13        for (int count : freq) {14            if (count > 0) {15                frequencyList.add(count);16            }17        }18 19        // Step 3: If distinct characters are already at most k, no deletions needed.20        int distinctCount = frequencyList.size();21        if (distinctCount <= k) {22            return 0;23        }24 25        // Step 4: Sort frequencies to find the smallest ones.26        Collections.sort(frequencyList);27 28        // Step 5: Sum the frequencies of the characters to be deleted.29        // We need to remove `distinctCount - k` characters.30        int deletions = 0;31        int charsToRemove = distinctCount - k;32        for (int i = 0; i < charsToRemove; i++) {33            deletions += frequencyList.get(i);34        }35 36        return deletions;37    }38}