题目描述
给你一个字符串 word
和一个整数 k
。
如果 |freq(word[i]) - freq(word[j])| <= k
对于字符串中所有下标 i
和 j
都成立,则认为 word
是 k 特殊字符串。
此处,freq(x)
表示字符 x
在 word
中的 出现频率,而 |y|
表示 y
的绝对值。
返回使 word
成为 k 特殊字符串 需要删除的字符的最小数量。
样例
输入:word = "aabcaba", k = 0
输出:3
解释:可以删除 2 个 "a" 和 1 个 "c" 使 word 成为 0 特殊字符串。
word 变为 "baba",此时 freq('a') == freq('b') == 2。
输入:word = "dabdcbdcdcd", k = 2
输出:2
解释:可以删除 1 个 "a" 和 1 个 "d" 使 word 成为 2 特殊字符串。
word 变为 "bdcbdcdcd",此时 freq('b') == 2,freq('c') == 3,freq('d') == 4。
输入:word = "aaabaaa", k = 2
输出:1
解释:可以删除 1 个 "b" 使 word 成为 2 特殊字符串。
因此,word 变为 "aaaaaa",此时每个字母的频率都是 6。
限制
1 <= word.length <= 10^5
0 <= k <= 10^5
word
仅由小写英文字母组成。
算法
(思维题) $O(n + |\Sigma|^2)$
- 求出每种字母的出现频率。
- 枚举一个出现频率作为频率的最小值 $m$,求出在这个限制下,需要删除的总数。如果一个字母的出现频率小于 $m$,则需要全部删除。否则,只需要删除到 $m + k$ 即可。
- 枚举时,更新删除总数的最小值。
时间复杂度
- 遍历字符串一次,时间复杂度为 $O(n)$。
- 共有 $O(|\Sigma|)$ 种频率,每种频率的处理时间也为 $O(|\Sigma|)$。
- 故总时间复杂度为 $O(n + |\Sigma|^2)$。
空间复杂度
- 需要 $O(|\Sigma|)$ 的额外空间存储频率。
C++ 代码
class Solution {
public:
int minimumDeletions(string word, int k) {
const int n = word.size();
vector<int> freq(26, 0);
for (char c : word)
++freq[c - 'a'];
int ans = INT_MAX;
for (int x : freq) {
int tot = 0;
for (int y : freq) {
if (y < x) tot += y;
else tot += max(0, y - x - k);
}
ans = min(ans, tot);
}
return ans;
}
};