leetcode 3085. 成为 K 特殊字符串需要删除的最少字符数 中等
给你一个字符串 word
和一个整数 k
。
如果 |freq(word[i]) - freq(word[j])| <= k
对于字符串中所有下标 i
和 j
都成立,则认为 word
是 k 特殊字符串。
此处,freq(x)
表示字符 x
在 word
中的出现频率,而 |y|
表示 y
的绝对值。
返回使 word
成为 k 特殊字符串 需要删除的字符的最小数量。
示例 1:
输入:word = "aabcaba", k = 0
输出:3
解释:可以删除 2
个 "a"
和 1
个 "c"
使 word
成为 0
特殊字符串。word
变为 "baba"
,此时 freq('a') == freq('b') == 2
。
示例 2:
输入:word = "dabdcbdcdcd", k = 2
输出:2
解释:可以删除 1
个 "a"
和 1
个 "d"
使 word
成为 2
特殊字符串。word
变为 "bdcbdcdcd"
,此时 freq('b') == 2
,freq('c') == 3
,freq('d') == 4
。
示例 3:
输入:word = "aaabaaa", k = 2
输出:1
解释:可以删除 1 个 "b"
使 word
成为 2
特殊字符串。因此,word
变为 "aaaaaa"
,此时每个字母的频率都是 6
。
提示:
1 <= word.length <= 10^5
0 <= k <= 10^5
word
仅由小写英文字母组成。
分析:由于 word 仅由小写英文字母组成,可以先用一个长度为 26 的数组,统计每个字符出现的次数。接着枚举所有出现次数不为 0 的字符,将该字符的出现次数作为最少出现次数,所有大于它出现次数的字符将被删除到符合条件,所有小于它出现次数的字符将被完全删除。最后返回最小删除次数即可。
int minimumDeletions(char* word, int k) {int cnt[30]={0};for(int i=0;word[i];++i)cnt[word[i]-'a']++;int sum=0x3fffffff;for(int i=0;i<26;++i){if(cnt[i]){int temp=cnt[i],count=0;for(int j=0;j<26;++j){if(cnt[j]){int b=cnt[j];if(temp>b)count+=b;else if(b>temp+k)count+=b-(temp+k);}}sum=fmin(count,sum);}}return sum;
}