Minimum Deletions to Make String K-Special
MedPrompt
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 <= 105wordconsists only of lowercase English letters.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves calculating the initial frequencies of all characters. Then, it iterates through every possible value for the minimum frequency (min_f) in the final k-special string, from 0 up to the maximum frequency found in the original string. For each min_f, it calculates the total deletions required to make all character frequencies fall within the range [min_f, min_f + k]. The minimum number of deletions found across all tested min_f values is the answer.
Algorithm
- Create an integer array
freqof size 26 to store character frequencies. - Iterate through the input
wordto populate thefreqarray and find the maximum frequencymax_freq. - Initialize
min_deletionsto the total number of characters in the word. - Loop a variable
floorfrom 0 up tomax_freq. Thisfloorrepresents the potential minimum frequency in the final k-special string. - Inside the loop, calculate the
current_deletionsrequired to make all character frequencies fit within the range[floor, floor + k]. - For each character frequency
fin thefreqarray:- If
f < floor, addftocurrent_deletions. - If
f > floor + k, addf - (floor + k)tocurrent_deletions.
- If
- After iterating through all character frequencies, update
min_deletions = min(min_deletions, current_deletions). - After the loop over
floorcompletes, returnmin_deletions.
Walkthrough
First, we compute the frequency of each of the 26 lowercase English letters in the input word. An array of size 26 can be used for this. We also find the maximum frequency max_freq among all characters. We initialize a variable min_deletions to a very large value (e.g., word.length()). We then loop through each possible lower bound floor from 0 to max_freq. Inside the loop, for a given floor, the target frequency range is [floor, floor + k]. We calculate the number of deletions needed for this range by iterating through the 26 character frequencies. For each frequency f, if it's below floor, we add f to the current deletions. If it's above floor + k, we add f - (floor + k). After calculating the total deletions for the chosen floor, we update our overall minimum. After the loop finishes, min_deletions will hold the result.
class Solution { public int minimumDeletions(String word, int k) { int[] freq = new int[26]; int maxFreq = 0; for (char c : word.toCharArray()) { freq[c - 'a']++; maxFreq = Math.max(maxFreq, freq[c - 'a']); } int minDeletions = word.length(); for (int floor = 0; floor <= maxFreq; floor++) { int currentDeletions = 0; int ceiling = floor + k; for (int f : freq) { if (f == 0) continue; if (f < floor) { currentDeletions += f; } else if (f > ceiling) { currentDeletions += f - ceiling; } } minDeletions = Math.min(minDeletions, currentDeletions); } return minDeletions; }}Complexity
Time
O(N + M * C), where N is the length of `word`, M is the maximum frequency of any character, and C is the alphabet size (26). Counting frequencies takes O(N). The nested loops take O(M * C). In the worst case, M can be up to N, leading to O(N*C).
Space
O(C), where C is the size of the alphabet (26). This is for storing the character frequencies.
Trade-offs
Pros
Simple to understand and implement.
Correct for all valid inputs.
Cons
Can be inefficient if the maximum frequency of a character is very large, as the outer loop's complexity depends on it.
This approach improves upon the brute-force method by observing that the optimal lower bound for the final frequency range must be related to the initial frequencies. Instead of checking every integer from 0 to max_freq, we only need to check values that correspond to the frequencies of characters present in the string. We can iterate through each unique non-zero frequency f as a potential lower bound min_f, calculate the deletions, and find the minimum. We also need to consider min_f = 0.
Algorithm
- First, calculate the frequencies of all characters in the
wordand store them in an arrayfreq. - Create a
Setto store all unique non-zero frequencies from thefreqarray. Add 0 to this set as well, as it's a valid lower bound for the final frequency range. - Initialize
min_deletionstoword.length(). - Iterate through each
floorvalue in the set of unique frequencies. - For each
floor, calculate thecurrent_deletionsneeded to bring all character frequencies into the range[floor, floor + k].- Iterate through all 26 frequencies
fin thefreqarray. - If
f < floor, addftocurrent_deletions. - If
f > floor + k, addf - (floor + k)tocurrent_deletions.
- Iterate through all 26 frequencies
- Update
min_deletions = min(min_deletions, current_deletions). - Return
min_deletions.
Walkthrough
The core idea is that the cost function (number of deletions) only changes its form when the lower bound floor or upper bound floor + k crosses one of the existing frequency values. Therefore, we only need to test floor values that are equal to one of the initial frequencies. The algorithm first computes all character frequencies. Then, it gathers all unique non-zero frequencies into a set and adds 0 to it. It then iterates through this set of unique frequencies. For each unique frequency u considered as the floor, it calculates the total deletions required and updates the minimum deletions found so far. This significantly reduces the number of iterations compared to the brute-force approach.
import java.util.*; class Solution { public int minimumDeletions(String word, int k) { int[] freq = new int[26]; for (char c : word.toCharArray()) { freq[c - 'a']++; } Set<Integer> uniqueFreqs = new HashSet<>(); uniqueFreqs.add(0); for (int f : freq) { if (f > 0) { uniqueFreqs.add(f); } } int minDeletions = word.length(); for (int floor : uniqueFreqs) { int currentDeletions = 0; int ceiling = floor + k; for (int f : freq) { if (f == 0) continue; if (f < floor) { currentDeletions += f; } else if (f > ceiling) { currentDeletions += f - ceiling; } } minDeletions = Math.min(minDeletions, currentDeletions); } return minDeletions; }}Complexity
Time
O(N + C^2), where N is the length of `word` and C is the alphabet size (26). Counting frequencies is O(N). There are at most C unique frequencies. For each unique frequency, we iterate through all C frequencies, resulting in O(C^2) for the main logic. Since C is a small constant, this is effectively O(N).
Space
O(C), where C is the alphabet size (26). This is for storing frequencies and the set of unique frequencies.
Trade-offs
Pros
Much more efficient than the brute-force approach.
Guaranteed to pass within time limits for the given constraints.
Cons
Involves a nested loop structure over the character set, which can be further optimized.
This is the most efficient approach. It builds upon the idea of checking only relevant lower bounds. By first sorting the character frequencies, we can calculate the number of deletions for each potential range much faster. We use prefix sums to quickly calculate the sum of frequencies that are too low. For frequencies that are too high, we can find them efficiently using binary search on the sorted frequency list and then use prefix sums to calculate the required deletions.
Algorithm
- Compute the frequencies of all characters and store the non-zero frequencies in a list
freqs. - Sort the
freqslist in ascending order. - Create a
prefix_sumarray forfreqs, whereprefix_sum[i]stores the sum of the firstifrequencies. - Initialize
min_deletionswith the cost of deleting all characters, which is the total sum of all frequencies (prefix_sum[n]). - Iterate
ifrom 0 ton-1, wherenis the number of unique character frequencies. In each iteration,freqs[i]is considered the minimum frequency of a character we keep. - For each
i:- Calculate
deletions_lower: the cost of deleting all characters with frequencies less thanfreqs[i]. This isprefix_sum[i]. - Define the target range as
[freqs[i], freqs[i] + k]. - Calculate
deletions_upper: the cost of reducing frequencies that are greater thanfreqs[i] + k. Find the first indexjwherefreqs[j] > freqs[i] + kusing binary search. The cost is(sum of freqs from j to n-1) - (number of such freqs) * (freqs[i] + k). This can be computed in O(1) using the prefix sum array after findingj. - The total deletions for this case is
deletions_lower + deletions_upper. - Update
min_deletionswith the minimum value found.
- Calculate
- Return
min_deletions.
Walkthrough
The key insight is that if we decide to keep a character with frequency f, to minimize deletions, we should make f the minimum frequency in our final set. This sets the target range to [f, f+k]. We can iterate through each of the original frequencies as this potential minimum. By sorting the frequencies first, we can efficiently calculate the costs. For each freqs[i] as the chosen minimum, all frequencies freqs[0...i-1] must be deleted (cost is prefix_sum[i]). For frequencies freqs[j] greater than freqs[i] + k, they must be reduced. We use binary search to find the block of such frequencies and prefix sums to calculate the deletion cost for them quickly. This avoids the O(C) inner loop of the previous approach.
import java.util.*; class Solution { public int minimumDeletions(String word, int k) { int[] freqArr = new int[26]; for (char c : word.toCharArray()) { freqArr[c - 'a']++; } List<Integer> freqs = new ArrayList<>(); for (int f : freqArr) { if (f > 0) { freqs.add(f); } } Collections.sort(freqs); if (freqs.isEmpty()) { return 0; } int n = freqs.size(); int[] prefixSum = new int[n + 1]; for (int i = 0; i < n; i++) { prefixSum[i + 1] = prefixSum[i] + freqs.get(i); } int minDeletions = prefixSum[n]; // Cost to delete all characters for (int i = 0; i < n; i++) { int currentDeletions = prefixSum[i]; // Delete all freqs smaller than freqs.get(i) int ceiling = freqs.get(i) + k; int j = findUpperBound(freqs, ceiling); if (j < n) { int sumOfLarger = prefixSum[n] - prefixSum[j]; int countOfLarger = n - j; currentDeletions += sumOfLarger - (countOfLarger * ceiling); } minDeletions = Math.min(minDeletions, currentDeletions); } return minDeletions; } private int findUpperBound(List<Integer> list, int target) { int low = 0, high = list.size(); while (low < high) { int mid = low + (high - low) / 2; if (list.get(mid) <= target) { low = mid + 1; } else { high = mid; } } return low; }}Complexity
Time
O(N + C log C), where N is the length of `word` and C is the alphabet size. O(N) for frequency counting, O(C log C) for sorting, and O(C log C) for the main loop with binary search. This is the optimal time complexity.
Space
O(C), where C is the alphabet size (26). Space is used for the frequency list and the prefix sum array.
Trade-offs
Pros
The most efficient algorithm with the best time complexity.
Scales very well with the problem constraints.
Cons
Slightly more complex to implement due to sorting, prefix sums, and binary search.
Solutions
Solution
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; }}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))class Solution {public: int minimumDeletions(string word, int k) { int freq[26]{}; for (char &c : word) { ++freq[c - 'a']; } vector<int> nums; for (int v : freq) { if (v) { nums.push_back(v); } } int n = word.size(); int ans = n; auto f = [&](int v) { int ans = 0; for (int x : nums) { if (x < v) { ans += x; } else if (x > v + k) { ans += x - v - k; } } return ans; }; for (int i = 0; i <= n; ++i) { ans = min(ans, f(i)); } return ans; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.