Medium

题目描述

给你一个长度为 n 的字符串 s 和一个相同长度的整数数组 cost，其中 cost[i] 是删除 s 的第 i 个字符的成本。

你可以从 s 中删除任意数量的字符（可能为零），使得结果字符串非空且由相等的字符组成。

返回所需的最小总删除成本。

示例 1：

输入：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。

示例 2：

输入：s = "abc", cost = [10,5,8]
输出：13
解释：
删除索引 1 和 2 处的字符得到字符串 "a"，该字符串由相等的字符组成，总成本为 cost[1] + cost[2] = 5 + 8 = 13。

示例 3：

输入：s = "zzzzz", cost = [67,67,67,67,67]
输出：0
解释：
s 中的所有字符都相等，所以删除成本为 0。

约束：

  • n == s.length == cost.length
  • 1 <= n <= 10^5
  • 1 <= cost[i] <= 10^9
  • s 由小写英文字母组成

解题思路

这道题的关键在于理解最终目标：保留所有相同的字符，删除其他字符，使得结果字符串只包含一种字符。

解题思路：

我们需要枚举每个可能保留的字符，计算保留该字符时的删除成本。对于每个字符 c，我们保留所有等于 c 的字符，删除其他所有字符。

具体步骤：

  1. 遍历字符串中的每个唯一字符作为最终保留的字符
  2. 对于每个选定的字符，计算删除其他所有字符的总成本
  3. 返回所有可能方案中成本最小的那个

优化思路： 可以先计算字符串的总成本，然后对于每个字符，计算保留该字符的成本（即该字符所有位置的成本之和），最小删除成本就是总成本减去最大的保留成本。

这种方法只需要遍历一次字符串，时间复杂度更优。

推荐解法： 使用哈希表统计每个字符的总成本，然后找出成本最大的字符进行保留。

代码实现

class Solution {
public:
    long long minCost(string s, vector<int>& cost) {
        unordered_map<char, long long> charCost;
        long long totalCost = 0;
        
        // 计算每个字符的总成本和整体总成本
        for (int i = 0; i < s.length(); i++) {
            charCost[s[i]] += cost[i];
            totalCost += cost[i];
        }
        
        // 找出成本最大的字符（保留它的成本最高）
        long long maxKeepCost = 0;
        for (auto& pair : charCost) {
            maxKeepCost = max(maxKeepCost, pair.second);
        }
        
        return totalCost - maxKeepCost;
    }
};

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        from collections import defaultdict
        
        char_cost = defaultdict(int)
        total_cost = 0
        
        # 计算每个字符的总成本和整体总成本
        for i in range(len(s)):
            char_cost[s[i]] += cost[i]
            total_cost += cost[i]
        
        # 找出成本最大的字符（保留它的成本最高）
        max_keep_cost = max(char_cost.values())
        
        return total_cost - max_keep_cost

public class Solution {
    public long MinCost(string s, int[] cost) {
        Dictionary<char, long> charCost = new Dictionary<char, long>();
        long totalCost = 0;
        
        // 计算每个字符的总成本和整体总成本
        for (int i = 0; i < s.Length; i++) {
            if (!charCost.ContainsKey(s[i])) {
                charCost[s[i]] = 0;
            }
            charCost[s[i]] += cost[i];
            totalCost += cost[i];
        }
        
        // 找出成本最大的字符（保留它的成本最高）
        long maxKeepCost = 0;
        foreach (var kvp in charCost) {
            maxKeepCost = Math.Max(maxKeepCost, kvp.Value);
        }
        
        return totalCost - maxKeepCost;
    }
}

/**
 * @param {string} s
 * @param {number[]} cost
 * @return {number}
 */
var minCost = function(s, cost) {
    const charCost = new Map();
    let totalCost = 0;
    
    // 计算每个字符的总成本和整体总成本
    for (let i = 0; i < s.length; i++) {
        const char = s[i];
        charCost.set(char, (charCost.get(char) || 0) + cost[i]);
        totalCost += cost[i];
    }
    
    // 找出成本最大的字符（保留它的成本最高）
    let maxKeepCost = 0;
    for (const [char, charTotalCost] of charCost) {
        maxKeepCost = Math.max(maxKeepCost, charTotalCost);
    }
    
    return totalCost - maxKeepCost;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)需要遍历一次字符串计算成本，其中 n 是字符串长度
空间复杂度O(1)哈希表最多存储 26 个小写字母，为常数空间