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.
Move from brute-force thinking to an efficient approach using hash map strategy.
You are given a string word and an integer k.
We consider word to be k-special if |freq(word[i]) - freq(word[j])| <= k for all indices i and j in the string.
Here, freq(x) denotes the frequency of the character x in word, and |y| denotes the absolute value of y.
Return the minimum number of characters you need to delete to make word k-special.
Example 1:
Input: word = "aabcaba", k = 0
Output: 3
Explanation: We can make word 0-special by deleting 2 occurrences of "a" and 1 occurrence of "c". Therefore, word becomes equal to "baba" where freq('a') == freq('b') == 2.
Example 2:
Input: word = "dabdcbdcdcd", k = 2
Output: 2
Explanation: We can make word 2-special by deleting 1 occurrence of "a" and 1 occurrence of "d". Therefore, word becomes equal to "bdcbdcdcd" where freq('b') == 2, freq('c') == 3, and freq('d') == 4.
Example 3:
Input: word = "aaabaaa", k = 2
Output: 1
Explanation: We can make word 2-special by deleting 1 occurrence of "b". Therefore, word becomes equal to "aaaaaa" where each letter's frequency is now uniformly 6.
Constraints:
1 <= word.length <= 1050 <= k <= 105word consists only of lowercase English letters.Problem summary: You are given a string word and an integer k. We consider word to be k-special if |freq(word[i]) - freq(word[j])| <= k for all indices i and j in the string. Here, freq(x) denotes the frequency of the character x in word, and |y| denotes the absolute value of y. Return the minimum number of characters you need to delete to make word k-special.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Hash Map · Greedy
"aabcaba" 0
"dabdcbdcdcd" 2
"aaabaaa" 2
minimum-deletions-to-make-character-frequencies-unique)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3085: Minimum Deletions to Make String K-Special
class Solution {
private List<Integer> nums = new ArrayList<>();
public int minimumDeletions(String word, int k) {
int[] freq = new int[26];
int n = word.length();
for (int i = 0; i < n; ++i) {
++freq[word.charAt(i) - 'a'];
}
for (int v : freq) {
if (v > 0) {
nums.add(v);
}
}
int ans = n;
for (int i = 0; i <= n; ++i) {
ans = Math.min(ans, f(i, k));
}
return ans;
}
private int f(int v, int k) {
int ans = 0;
for (int x : nums) {
if (x < v) {
ans += x;
} else if (x > v + k) {
ans += x - v - k;
}
}
return ans;
}
}
// Accepted solution for LeetCode #3085: Minimum Deletions to Make String K-Special
func minimumDeletions(word string, k int) int {
freq := [26]int{}
for _, c := range word {
freq[c-'a']++
}
nums := []int{}
for _, v := range freq {
if v > 0 {
nums = append(nums, v)
}
}
f := func(v int) int {
ans := 0
for _, x := range nums {
if x < v {
ans += x
} else if x > v+k {
ans += x - v - k
}
}
return ans
}
ans := len(word)
for i := 0; i <= len(word); i++ {
ans = min(ans, f(i))
}
return ans
}
# Accepted solution for LeetCode #3085: Minimum Deletions to Make String K-Special
class Solution:
def minimumDeletions(self, word: str, k: int) -> int:
def f(v: int) -> int:
ans = 0
for x in nums:
if x < v:
ans += x
elif x > v + k:
ans += x - v - k
return ans
nums = Counter(word).values()
return min(f(v) for v in range(len(word) + 1))
// Accepted solution for LeetCode #3085: Minimum Deletions to Make String K-Special
impl Solution {
pub fn minimum_deletions(word: String, k: i32) -> i32 {
let mut freq = [0; 26];
for c in word.chars() {
freq[(c as u8 - b'a') as usize] += 1;
}
let mut nums = vec![];
for &v in freq.iter() {
if v > 0 {
nums.push(v);
}
}
let n = word.len() as i32;
let mut ans = n;
for i in 0..=n {
let mut cur = 0;
for &x in nums.iter() {
if x < i {
cur += x;
} else if x > i + k {
cur += x - i - k;
}
}
ans = ans.min(cur);
}
ans
}
}
// Accepted solution for LeetCode #3085: Minimum Deletions to Make String K-Special
function minimumDeletions(word: string, k: number): number {
const freq: number[] = Array(26).fill(0);
for (const ch of word) {
++freq[ch.charCodeAt(0) - 97];
}
const nums = freq.filter(x => x > 0);
const f = (v: number): number => {
let ans = 0;
for (const x of nums) {
if (x < v) {
ans += x;
} else if (x > v + k) {
ans += x - v - k;
}
}
return ans;
};
return Math.min(...Array.from({ length: word.length + 1 }, (_, i) => f(i)));
}
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.