2026-05-02：使所有字符相等的最小删除代价。用go语言，给定一个字符串 s（长度为 n）和一个数组 cost。其中 cost[i] 表示删除 s 中第 i 个字符所需要的代价。你可以任意选择要
2026-05-02：使所有字符相等的最小删除代价。用go语言，给定一个字符串 s（长度为 n）和一个数组 cost。其中 cost[i] 表示删除 s 中第 i 个字符所需要的代价。你可以任意选择要删除哪些字符（可以删除任意多个，也可以不删），但最终得到的字符串必须满足两点：
1）不能是空串；
2）最终字符串的所有字符都要相同（即由某一种字符重复组成）。
问：为了达到上述条件，最小的删除总代价是多少？
n == s.length == cost.length。
1 <= n <= 100000。
1 <= cost[i] <= 1000000000。
s 仅由小写英文字母组成。
输入： s = “aabaac”, cost = [1,2,3,4,1,10]。
输出： 11。
解释：
删除索引为 0、1、2、3 和 4 的字符后，字符串变为 “c”，它由相同的字符组成，总删除代价为：cost[0] + cost[1] + cost[2] + cost[3] + cost[4] = 1 + 2 + 3 + 4 + 1 = 11。
题目来自力扣3784。
代码解题过程分步详细描述
第一步：理解核心解题思路
题目要求最终字符串所有字符相同且非空，最小删除代价等价于：
选择保留某一种字符（a-z中的一种），删除其他所有字符，计算每种选择的删除代价，最终取最小代价。
反向推导更简单：
总删除代价 = 所有字符的删除代价总和 - 保留字符的总代价（保留的字符不需要删除，减去这部分就是删除其他字符的代价）。
因此，要让删除代价最小，就需要让保留字符的总代价最大。
第二步：计算所有字符的总删除代价
遍历字符串和代价数组，把每一个字符的删除代价全部加起来，得到总代价。
- 字符：a a b a a c
- 代价：1 2 3 4 1 10
- 总代价 = 1+2+3+4+1+10 =21
第三步：统计每种小写字母的总代价
创建26个位置（对应a-z），分别累加每一种字符对应的所有删除代价：
- 字符a：出现在索引0、1、3、4，代价总和 = 1+2+4+1 =8
- 字符b：出现在索引2，代价总和 =3
- 字符c：出现在索引5，代价总和 =10
- 其余字母（d-z）：没有出现，代价总和 = 0
最终统计结果：a=8，b=3，c=10，其余=0
第四步：找到代价最大的字符
从26个字母的总代价中，找出数值最大的那个值：
对比 8、3、10、0…，最大值是10（对应字符c）。
第五步：计算最小删除代价
用总代价减去最大保留代价，就是最终答案：
最小删除代价 = 21 - 10 =11，和题目输出一致。
时间复杂度与额外空间复杂度分析
1. 时间复杂度
- 遍历字符串和代价数组，统计总代价、各字母代价：O(n)（n是字符串长度）
- 查找26个字母中的最大值：O(1)（固定26个元素，与n无关）
- 总体时间复杂度：O(n)，能高效处理n≤100000的场景。
2. 额外空间复杂度
- 仅使用了固定大小的数组
[26]int、几个变量（total、遍历索引等） - 额外空间不随输入规模n变化，属于常数级空间
- 总体额外空间复杂度：O(1)
总结
- 解题核心：总代价 - 最大单字符代价 = 最小删除代价；
- 时间复杂度O(n)，线性遍历一次即可完成计算；
- 额外空间复杂度O(1)，仅使用固定大小的辅助空间。
Go完整代码如下：
packagemainimport("fmt""slices")funcminCost(sstring,cost[]int)int64{total:=0sum:=[26]int{}fori,x:=rangecost{total+=x sum[s[i]-'a']+=x}returnint64(total-slices.Max(sum[:]))}funcmain(){s:="aabaac"cost:=[]int{1,2,3,4,1,10}result:=minCost(s,cost)fmt.Println(result)}Python完整代码如下：
# -*-coding:utf-8-*-defminCost(s:str,cost:list[int])->int:total=0sum_list=[0]*26fori,xinenumerate(cost):total+=x sum_list[ord(s[i])-ord('a')]+=xreturntotal-max(sum_list)defmain():s="aabaac"cost=[1,2,3,4,1,10]result=minCost(s,cost)print(result)if__name__=="__main__":main()C++完整代码如下：
#include<iostream>#include<vector>#include<algorithm>#include<numeric>longlongminCost(std::string s,std::vector<int>&cost){longlongtotal=0;std::vector<int>sum(26,0);for(inti=0;i<cost.size();i++){total+=cost[i];sum[s[i]-'a']+=cost[i];}returntotal-*std::max_element(sum.begin(),sum.end());}intmain(){std::string s="aabaac";std::vector<int>cost={1,2,3,4,1,10};longlongresult=minCost(s,cost);std::cout<<result<<std::endl;return0;}