Minimum Deletions to Make String K-Special
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 = 0Output
3Deleting 2 occurrences of
"a" and 1 occurrence of "c" makes the remaining word have freq('a') == freq('b') == 2.Example 2
Input
word = "dabdcbdcdcd", k = 2Output
2Deleting 1 occurrence of
"a" and 1 occurrence of "d" leaves frequencies freq('b') == 2, freq('c') == 3, and freq('d') == 4, whose differences are at most 2.Constraints
- 1 <= word.length <= 10^5
- 0 <= k <= 10^5
- word consists only of lowercase English letters.