2024-10-08：用go语言，给定一个字符串 word 和一个整数 k，判断是否可以通过删除最少数量的字符使得该字符串成为 k 特殊字符串。

其中，k 特殊字符串满足字符串中任意两个字符的出现频率之差的绝对值均不超过 k。

你可以编写一个算法来计算最少需要删除多少个字符，使得给定的字符串 word 成为 k 特殊字符串。

输入：word = "aabcaba", k = 0。

输出：3。

解释：可以删除 2 个 "a" 和 1 个 "c" 使 word 成为 0 特殊字符串。word 变为 "baba"，此时 freq('a') == freq('b') == 2。

答案2024-10-08：

chatgpt

题目来自leetcode3085。

大体步骤如下：

1.创建一个长度为26的整型切片cnt，用来统计单词word中每个字母出现的次数。

2.将cnt中的值进行排序，使得它们按照出现次数递减的顺序排列。

3.初始化变量maxSave为 0，用来记录最大的节省字符数。

4.遍历经过排序后的cnt切片，对于每个字母出现的次数 base：

• •初始化变量sum为 0，用来记录在保留 base+k 个字符的情况下的总字符数量。
• •对从当前位置开始的 cnt 切片进行遍历，将出现的字符次数与 base+k 中的较小值累加至sum。
• •更新maxSave为sum与当前maxSave中的较大值。

5.计算最终需要删除的字符数量，即 len(word) 减去maxSave的值。

总的时间复杂度：在代码中，排序操作应该是最耗时的部分，时间复杂度为 O(nlog(n))，n 为单词长度。接下来的遍历操作的时间复杂度为 O(26 * n)，因为对于每个字符，我们需要对 cnt 切片进行遍历。最终总的时间复杂度为 O(nlog(n) + 26n)，约等于 O(nlog(n))。

总的额外空间复杂度：除了输入参数外，代码中使用了长度为26的整型切片 cnt，因此额外空间复杂度为 O(26)（常量级别）。

go完整代码如下：

packagemain

import(
"fmt"
"slices"
)

funcminimumDeletions(wordstring,kint)int{
cnt:=make([]int,26)
for_,b:=rangeword{
cnt[b-'a']++
}
slices.Sort(cnt)

maxSave:=0
fori,base:=rangecnt{
sum:=0
for_,c:=rangecnt[i:]{
sum+=min(c,base+k)//至多保留base+k个
}
maxSave=max(maxSave,sum)
}
returnlen(word)-maxSave
}
funcmain(){
word:="aabcaba"
k:=0
fmt.Println(minimumDeletions(word,k))
}

rust完整代码如下：

usestd::cmp::{max,min};

fnminimum_deletions(word:&str,k:i32)->i32{
letmutcnt:[i32;26]=[0;26];
forbinword.chars(){
cnt[(basu8-b'a')asusize]+=1;
}
slice_sort(&mutcnt);

letmutmax_save=0;
for(i,&base)incnt.iter().enumerate(){
letmutsum=0;
for&cin&cnt[i..]{
sum+=min(c,base+k);//最多保留base+k个
}
max_save=max(max_save,sum);
}
(word.len()asi32)-max_save
}

fnslice_sort(slice:&mut[i32;26]){
slice.sort_unstable();
}

fnmain(){
letword="aabcaba";
letk=0;
println!("{}",minimum_deletions(word,k));
}