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. 1. 字符a：出現在索引0、1、3、4，代價總和 = 1+2+4+1 =8

2. 2. 字符b：出現在索引2，代價總和 =3

3. 3. 字符c：出現在索引5，代價總和 =10

4. 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的場景。

• ? 僅使用了固定大小的數組[26]int、幾個變量（total、遍歷索引等）

• ? 額外空間不隨輸入規模n變化，屬于常數級空間

• ? 總體額外空間復雜度：O(1)

1. 1. 解題核心：總代價 - 最大單字符代價 = 最小刪除代價；

2. 2. 時間復雜度O(n)，線性遍歷一次即可完成計算；

3. 3. 額外空間復雜度O(1)，僅使用固定大小的輔助空間。

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助力您的未來發展。