Mutating counts without cleanup
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Build confidence with an intuition-first walkthrough focused on hash map fundamentals.
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 summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Hash Map · Greedy
"abc" 2
"aabb" 2
"yyyzz" 1
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3545: Minimum Deletions for At Most K Distinct Characters
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;
}
}
// Accepted solution for LeetCode #3545: Minimum Deletions for At Most K Distinct Characters
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
}
# Accepted solution for LeetCode #3545: Minimum Deletions for At Most K Distinct Characters
class Solution:
def minDeletion(self, s: str, k: int) -> int:
return sum(sorted(Counter(s).values())[:-k])
// Accepted solution for LeetCode #3545: Minimum Deletions for At Most K Distinct Characters
fn min_deletion(s: String, k: i32) -> i32 {
use std::collections::HashMap;
let mut v : Vec<_> = s.chars().fold(HashMap::new(), |mut acc, c| {
*acc.entry(c).or_insert(0) += 1;
acc
}).into_values().collect();
v.sort_unstable();
let k = k as usize;
if v.len() <= k {
0
} else {
let n = v.len() - k;
v.into_iter().take(n).sum()
}
}
fn main() {
let ret = min_deletion("abc".to_string(), 2);
println!("ret={ret}");
}
#[test]
fn test() {
assert_eq!(min_deletion("abc".to_string(), 2), 1);
assert_eq!(min_deletion("aabb".to_string(), 2), 0);
}
// Accepted solution for LeetCode #3545: Minimum Deletions for At Most K Distinct Characters
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);
}
Use this to step through a reusable interview workflow for this problem.
Try every possible combination of choices. With n items each having two states (include/exclude), the search space is 2ⁿ. Evaluating each combination takes O(n), giving O(n × 2ⁿ). The recursion stack or subset storage uses O(n) space.
Greedy algorithms typically sort the input (O(n log n)) then make a single pass (O(n)). The sort dominates. If the input is already sorted or the greedy choice can be computed without sorting, time drops to O(n). Proving greedy correctness (exchange argument) is harder than the implementation.
Review these before coding to avoid predictable interview regressions.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Wrong move: Locally optimal choices may fail globally.
Usually fails on: Counterexamples appear on crafted input orderings.
Fix: Verify with exchange argument or monotonic objective before committing.