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.
This approach involves checking all possible combinations to find those that satisfy the conditions of the problem. Although not the most efficient, it ensures all possibilities are covered.
The function iterates over all pairs of elements in the array, checking if their sum equals the target value. If it does, it prints the pair.
Time Complexity: O(n^2)
Space Complexity: O(1)
This approach leverages a hash map to store elements and their indices. By checking for the complement (target - current element) during traversal, we reduce the time complexity significantly.
This solution uses an array to simulate a hash map, storing whether an element exists while traversing.
Time Complexity: O(n)
Space Complexity: O(n)
First, we can count the occurrence of each character in the string and put all the counts into an array nums. Since the string only contains lowercase letters, the length of the array nums will not exceed 26.
Next, we can enumerate the minimum frequency v of characters in the K special strings within the range [0,..n], and then use a function f(v) to calculate the minimum number of deletions to adjust the frequency of all characters to v. The minimum value of all f(v) is the answer.
The calculation method of function f(v) is as follows:
Traverse each element x in the array nums. If x < v, it means that we need to delete all characters with a frequency of x, and the number of deletions is x. If x > v + k, it means that we need to adjust all characters with a frequency of x to v + k, and the number of deletions is x - v - k. The sum of all deletion counts is the value of f(v).
The time complexity is O(n times |\Sigma|), and the space complexity is O(|\Sigma|). Here, n is the length of the string, and |\Sigma| is the size of the character set. In this problem, |\Sigma| = 26.
| Approach | Complexity |
|---|---|
| Approach 1: Brute Force Search | Time Complexity: O(n^2) |
| Approach 2: Hash Map for Quick Lookup | Time Complexity: O(n) |
| Counting + Enumeration | — |
| 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 |
Minimum Deletions to Make String K-Special | 2 Simple Approaches | Leetcode 3085 | codestorywithMIK • codestorywithMIK • 12,362 views views
Watch 9 more video solutions →Practice Minimum Deletions to Make String K-Special with our built-in code editor and test cases.
Practice on FleetCode