2026-05-02：使所有字符相等的最小删除代价。用go语言，给定一个字符串 s（长度为 n）和一个数组 cost。其中 cost[i] 表示删除 s…

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），分别累加每一种字符对应的所有删除代价：

1. 字符a：出现在索引0、1、3、4，代价总和 = 1+2+4+1 =8

2. 字符b：出现在索引2，代价总和 =3

3. 字符c：出现在索引5，代价总和 =10

4. 其余字母（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)

总结

1. 解题核心：总代价 – 最大单字符代价 = 最小删除代价；

2. 时间复杂度O(n)，线性遍历一次即可完成计算；

3. 额外空间复杂度O(1)，仅使用固定大小的辅助空间。

Go完整代码如下：

package main

 import (
    "fmt"
    "slices"
)

 func minCost(s string, cost []int)int64 {
    total := 0
    sum := [26]int{}
    for i, x := range cost {
        total += x
        sum[s[i]-'a'] += x
    }
    returnint64(total - slices.Max(sum[:]))
}

 func main() {
    s := "aabaac"
    cost := []int{1, 2, 3, 4, 1, 10}
    result := minCost(s, cost)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 def minCost(s: str, cost: list[int]) -> int:
    total = 0
    sum_list = [0] * 26
    for i, x in enumerate(cost):
        total += x
        sum_list[ord(s[i]) - ord('a')] += x
    return total - max(sum_list)

 def main():
    s = "aabaac"
    cost = [1, 2, 3, 4, 1, 10]
    result = minCost(s, cost)
    print(result)

 if __name__ == "__main__":
    main()

C++完整代码如下：

  

  

   


 long long minCost(std::string s, std::vector& cost) {
    long long total = 0;
    std::vector sum(26, 0);

     for (int i = 0; i < cost.size(); i++) {
        total += cost[i];
        sum[s[i] - 'a'] += cost[i];
    }

     return total - *std::max_element(sum.begin(), sum.end());
}

 int main() {
    std::string s = "aabaac";
    std::vector cost = {1, 2, 3, 4, 1, 10};
    long long result = minCost(s, cost);
    std::cout << result << std::endl;
    return0;
}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。