Is Minimum Deletions to Make String K-Special easy or hard?

Minimum Deletions to Make String K-Special is rated Medium. The challenge is identifying that you should operate on character frequencies rather than the string itself, then apply greedy trimming so all frequencies stay within a difference of k.

Minimum Deletions to Make String K-Special Python/Java solution

The typical Python or Java implementation builds a frequency map using a dictionary or array of size 26, extracts the counts, sorts them, and evaluates the minimum deletions for each candidate baseline frequency. Both languages implement the same greedy trimming logic and run in O(n) overall time.

How to solve Minimum Deletions to Make String K-Special in O(n)?

First compute the frequency of each character in O(n). Then iterate through possible baseline frequencies and calculate deletions by removing characters below the baseline and trimming those above baseline + k. Since the alphabet size is fixed (26), the additional work is constant, making the effective complexity linear in the string length.

What is the best approach for Minimum Deletions to Make String K-Special?

The best approach counts character frequencies with a hash map, sorts the frequency list, and greedily enforces the constraint that all frequencies stay within a window of size k. For each possible baseline frequency, characters below it are removed and characters above baseline + k are trimmed. Because there are at most 26 characters, this runs in about O(26 log 26) time and O(26) space.

Is Minimum Deletions to Make String K-Special asked at Google/Amazon/Meta?

Problems involving frequency balancing, greedy deletions, and hash-map counting frequently appear in interviews at companies like Amazon, Google, and Meta. Variants of this problem test understanding of string frequency constraints and greedy optimization.

What data structure is used in Minimum Deletions to Make String K-Special?

A hash table or fixed-size frequency array is used to count how many times each character appears. After counting, an array or list of frequencies is processed with sorting and greedy adjustments to enforce the k-difference constraint.

What is the time complexity of Minimum Deletions to Make String K-Special?

The optimal solution runs in O(n + 26 log 26) time where n is the string length. O(n) is used to count frequencies, and sorting at most 26 character counts costs O(26 log 26). Space complexity is O(26) for the frequency table.

Description Hints 4 Solution Video 37:11

3085. Minimum Deletions to Make String K-Special

Medium67.2% acceptance3 companies

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 <= 10⁵
0 <= k <= 10⁵
word consists only of lowercase English letters.

Asked at 3 companies

D. E. Shaw

Google Bloomberg

Topics

Hints open one at a time

Hint 1

Count the frequency of each letter.

Hint 2

Suppose we select several characters as the final answer, and let x be the character with the smallest frequency in the answer. It can be shown that out of the selected characters, the optimal solution will never delete an occurrence of character x to obtain the answer.

Hint 3

We will fix a character c and assume that it will be the character with the smallest frequency in the answer. Suppose its frequency is x.

Hint 4

Then, for every other character, we will count the number of occurrences that will be deleted. Suppose that the current character has y occurrences.

If y < x, we need to delete all of them.
if y > x + k, we should delete y - x - k of such character.
Otherwise we don’t need to delete it.

37:11

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution