Minimum Deletions for At Most K Distinct Characters solution and explanation
Google
9 more videos on this problem
LeetCode#3545 Minimum Deletions for At Most K Distinct Characters - PythonCodeJulian · 1:00 · 1K views
3545. Minimum Deletions for At Most K Distinct Characters (Leetcode Easy)Programming Live with Larry · 3:58 · 671 views
Minimum Deletions for At Most K Distinct Characters | Weekly Contest 449 | Java | Developer CoderDeveloper Coder · 6:29 · 302 views
Minimum Deletions for Atmost K distinct Characters Weekly Contest 449 LeetCode 3545R Sai Siddhu · 7:42 · 202 views
leetcode 3545 Minimum Deletions for At Most K Distinct Characters | heapCode-Yao · 5:07 · 127 views
Leetcode 3545. Minimum Deletions for At Most K Distinct Characters || Weekly Contest 449ExpertFunda · 20:44 · 93 views
Leetcode 3545 Minimum Deletions for At Most K Distinct CharactersAlgorithmicIQ · 12:53 · 83 views
Minimum Deletions for At Most K Distinct Characters | Leetcode 3545 | HindiAnubhav Ghosh · 2:19 · 71 views
Day 680: LeetCode Problem 3545. Minimum Deletions for At Most K Distinct Characters - SwiftiOSxBank · 9:16 · 34 views
3545 Minimum Deletions for At Most K Distinct CharactersByte By Byte · 7:07 · 17 views
The 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:
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.
Solution
We can use an array cnt to count the frequency of each character. Then, we sort this array and return the sum of the first 26 - k elements.
The time complexity is O(|\Sigma| times log |\Sigma|), and the space complexity is O(|\Sigma|), where |\Sigma| is the size of the character set. In this problem, |\Sigma| = 26.
class Solution:
def minDeletion(self, s: str, k: int) -> int:
return sum(sorted(Counter(s).values())[:-k])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;
}
}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;
}
};function minDeletion(s: string, k: number): number {
const cnt: number[] = Array(26).fill(0);
for (const c of s) {
++cnt[c.charCodeAt(0) - 97];
}
cnt.sort((a, b) => a - b);
return cnt.slice(0, 26 - k).reduce((a, b) => a + b, 0);
}func minDeletion(s string, k int) (ans int) {
cnt := make([]int, 26)
for _, c := range s {
cnt[c-'a']++
}
sort.Ints(cnt)
for i := 0; i+k < len(cnt); i++ {
ans += cnt[i]
}
return
}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. |
Frequently asked questions
Is Minimum Deletions for At Most K Distinct Characters easy or hard?
The problem is generally classified as Easy because it relies on basic string traversal and frequency counting. The main insight is recognizing the greedy strategy: remove the least frequent character types first to minimize deletions.
Minimum Deletions for At Most K Distinct Characters Python/Java solution
Most implementations follow the same pattern across languages: count characters with a map or dictionary, store the frequencies, sort them, and sum the smallest frequencies until only K distinct characters remain. This approach translates directly to Python, Java, C++, Go, and TypeScript with minimal changes.
How to solve Minimum Deletions for At Most K Distinct Characters in O(n)?
First count character frequencies in O(n) using a hash table. If the number of unique characters is greater than K, sort the frequencies or use a min heap to remove the smallest frequency groups until only K remain. The counting step is O(n), and the greedy removal step adds O(m log m) where m is the number of distinct characters.
What is the best approach for Minimum Deletions for At Most K Distinct Characters?
The best approach uses frequency counting with a greedy strategy. Count each character using a hash map, sort the frequencies, and delete the smallest ones until only K distinct characters remain. This keeps high-frequency characters and minimizes deletions. The overall time complexity is O(n + m log m), where m is the number of distinct characters.
Is Minimum Deletions for At Most K Distinct Characters asked at Google/Amazon/Meta?
This pattern appears frequently in interviews at companies like Amazon, Google, and Meta because it tests string processing, frequency counting, and greedy optimization. Variations of the problem also appear in discussions about limiting distinct elements or optimizing deletions in strings.
What data structure is used in Minimum Deletions for At Most K Distinct Characters?
The core data structure is a hash table (or dictionary) to count character frequencies. After counting, a sorted list of frequencies or a min heap is used to greedily remove the least frequent characters. These structures make it efficient to track and eliminate character groups.
What is the time complexity of Minimum Deletions for At Most K Distinct Characters?
The optimal solution runs in O(n + m log m) time. O(n) is used to count character frequencies in the string, and O(m log m) is required to sort the frequency list (or operate a min heap). Space complexity is O(m) for storing character counts.