Watch 10 video solutions for Minimum Deletions for At Most K Distinct Characters, a easy level problem involving Hash Table, String, Greedy. This walkthrough by CodeJulian has 1,647 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.k = 2 distinct characters, remove all occurrences of any one character from the string.'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.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.k = 1 distinct character, remove all occurrences of any one character from the string.'z' results in at most k distinct characters. Thus, the answer is 2.
Constraints:
1 <= s.length <= 161 <= k <= 16s consists only of lowercase English letters.
Problem Overview: Given a string s and an integer k, delete the minimum number of characters so the resulting string contains at most k distinct characters. The key decision is which character types to remove entirely so the total deletions stay minimal.
The problem is essentially about frequency management. If the string already has <= k unique characters, no deletion is required. When there are more than k distinct characters, you must completely remove some character types. The optimal strategy keeps the characters that appear most frequently and removes the ones with the smallest counts.
Approach 1: Counting + Sorting (Greedy) (Time: O(n + m log m), Space: O(m))
Use a hash table to count the frequency of every character in the string. Let m be the number of distinct characters. If m <= k, return 0 immediately. Otherwise, collect all frequencies into a list and sort it in ascending order using a sorting algorithm. Greedily delete the least frequent characters first by summing the smallest frequencies until only k character types remain. This works because removing a rare character costs fewer deletions than removing a frequent one.
The greedy insight is straightforward: keeping high-frequency characters maximizes the remaining string length while minimizing deletions. Sorting ensures you always remove the cheapest character types first.
Approach 2: Counting + Min Heap (Greedy) (Time: O(n + m log m), Space: O(m))
Instead of sorting the entire frequency list, push all character counts into a min-heap. While the heap size is greater than k, repeatedly pop the smallest frequency and add it to the deletion count. Each pop removes one character type completely. The heap always exposes the cheapest removal candidate, which preserves the greedy property.
This approach is useful when frequencies are generated incrementally or when you want to avoid sorting the full list. The logic remains the same: eliminate the least frequent character types first.
Recommended for interviews: Counting + Sorting is the most common solution. It clearly demonstrates understanding of frequency counting with a hash map and greedy optimization. Interviewers expect you to recognize that removing entire low-frequency character groups minimizes deletions. Mentioning the heap alternative shows deeper familiarity with greedy data-structure patterns.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Counting + Sorting (Greedy) | O(n + m log m) | O(m) | General solution. Simple implementation using frequency array or hash map followed by sorting. |
| Counting + Min Heap | O(n + m log m) | O(m) | Useful when you want incremental greedy removal without sorting the full frequency list. |
| Brute Force Character Removal | O(n * m) | O(m) | Conceptual baseline for understanding; tries removing different character sets but inefficient for large inputs. |