3085. Minimum Deletions to Make String K-Special
Description
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 <= 105
0 <= k <= 105
word
consists only of lowercase English letters.
Solutions
Solution 1: Counting + Enumeration
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$.
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|