解题思路
一开始这道题我是想着
- 首先统计出每个字符串的个数
- 通过排序然后滑动窗口找到能使窗口最长的个数数组
- 最后删除不符合字符串
但这个思路有几个问题
- 首先不能解决删除某个元素后窗口变化后，如何重新选择窗口问题
- 窗口的边界问题，若选择大于k处进行滑动窗口，那不知道排除的是次数最小值还是最大值
正解
考虑保存最多字母
- 由于只有26个字母，所以可以考虑建个数组保存每个字符出现的次数
- 枚举每个字符出现的次数，假设当前的字符出现次数是最少的，那么应该最多的字符应该在
min(c,base+k) - 尽量保存最长的字符串所以要保留
res = max(res,maxtmp)
func minimumDeletions(word string, k int) int {
cnt := make([]int, 26)
for _, b := range word {
cnt[b-'a']++
}
slices.Sort(cnt)
maxSave := 0
for i, base := range cnt {
sum := 0
for _, c := range cnt[i:] {
sum += min(c, base+k) // 至多保留 base+k 个
}
maxSave = max(maxSave, sum)
}
return len(word) - maxSave //取反
}
