Watch 10 video solutions for Minimum Deletions to Make String K-Special, a medium level problem involving Hash Table, String, Greedy. This walkthrough by codestorywithMIK has 12,362 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 Overview: You are given a string s and an integer k. A string is k‑special if the difference between the frequencies of any two characters is at most k. You can delete characters from the string. The goal is to compute the minimum deletions required so the remaining character frequencies satisfy this constraint.
Approach 1: Brute Force Search (O(26²) time, O(26) space)
Start by counting the frequency of every character using a hash map or fixed array of size 26. Treat each possible frequency as the baseline minimum frequency you want to keep. For a chosen base f, every character with frequency less than f must be fully deleted, while characters with frequency greater than f + k must be reduced down to f + k. Iterate through all candidate base frequencies and compute the deletions required for each. The smallest deletion count is the answer. This approach works because the alphabet size is small, but it still evaluates many redundant cases.
Approach 2: Hash Map for Quick Lookup (Greedy + Sorting) (O(26 log 26) time, O(26) space)
First count character frequencies using a hash table. Extract the frequency values and sort them using sorting. Now iterate through the sorted frequencies and treat each value as the minimum allowed frequency. For every other frequency, apply a greedy adjustment: delete the entire character if its count is below the baseline, or trim it down to baseline + k if it exceeds the allowed range. Because the list is sorted, you can compute deletions efficiently with simple iteration. The greedy rule works because keeping frequencies within a sliding window of size k minimizes unnecessary deletions.
This strategy combines greedy reasoning with frequency counting. Since there are at most 26 distinct characters, the algorithm is effectively constant time for real inputs while remaining clean and interview-friendly.
Recommended for interviews: Interviewers usually expect the frequency-count + greedy adjustment approach. Showing the brute force baseline demonstrates that you understand the constraint mathematically, but implementing the sorted frequency or hash map optimization shows stronger algorithmic thinking and awareness of counting-based string techniques.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Search over Frequencies | O(26²) | O(26) | Good for understanding the constraint and testing every possible baseline frequency |
| Hash Map + Greedy Adjustment with Sorting | O(26 log 26) | O(26) | Best general solution; efficient frequency analysis with simple greedy trimming |