Minimum Deletions for At Most K Distinct Characters - Video Solutions
LeetCode#3545 Minimum Deletions for At Most K Distinct Characters - Python
Minimum Deletions for At Most K Distinct Characters - Video Solution
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,656 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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:
shas three distinct characters:'a','b'and'c', each with a frequency of 1.- Since we can have at most
k = 2distinct characters, remove all occurrences of any one character from the string. - For example, removing all occurrences of
'c'results in at mostkdistinct characters. Thus, the answer is 1.
Example 2:
Input: s = "aabb", k = 2
Output: 0
Explanation:
shas two distinct characters ('a'and'b') with frequencies of 2 and 2, respectively.- Since we can have at most
k = 2distinct characters, no deletions are required. Thus, the answer is 0.
Example 3:
Input: s = "yyyzz", k = 1
Output: 2
Explanation:
shas two distinct characters ('y'and'z') with frequencies of 3 and 2, respectively.- Since we can have at most
k = 1distinct character, remove all occurrences of any one character from the string. - Removing all
'z'results in at mostkdistinct characters. Thus, the answer is 2.
Constraints:
1 <= s.length <= 161 <= k <= 16sconsists only of lowercase English letters.
Approach Overview
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.
Complexity Analysis
| 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. |