题目描述

给定一个字符串 s 和一个整数数组 cost，其中 cost[i] 是从 s 中删除字符 i 的代价。

返回使字符串任意相邻两个字母不相同的最小删除成本。

请注意，删除一个字符后，删除其他字符的成本不会改变。

样例

输入：s = "abaac", cost = [1,2,3,4,5]
输出：3
解释：删除字母 "a" 的成本为 3，然后得到 "abac"（字符串中相邻两个字母不相同）。

输入：s = "abc", cost = [1,2,3]
输出：0
解释：无需删除任何字母，因为字符串中不存在相邻两个字母相同的情况。

输入：s = "aabaa", cost = [1,2,3,4,1]
输出：2
解释：删除第一个和最后一个字母，得到字符串 ("aba")。

限制

• s.length == cost.length
• `1 <= s.length, cost.length <= 10^5``
• 1 <= cost[i] <= 10^4
• s 中只含有小写英文字母。

算法1

(动态规划) $O(n)$

1. 设状态 $f(i, j)$ 表示考虑了前 $i$ 个字符，以字符 $j$ 结尾的最小代价。假设这里 $i$ 有效下标从 1 开始。
2. 初始时，哨兵位置 $f(0, j) = 0$，其余为正无穷。
3. 转移时，对于当前位置 $i$ 和结尾的字符 $j$，如果删除第 $i$ 个字符，则转移 $f(i, j) = \min(f(i, j), f(i-1, j) + cost(i))$；如果当前字符 $k$ 与 $j$ 不同，则可以不删除，转移 $f(i, k) = \min(f(i, k), f(i-1, j))$。
4. 最终答案为 $\min(f(n, j))$。

时间复杂度

• 由于字符只有 26 种，所以状态数为 $O(n)$，转移时间为常数，故总时间复杂度为 $O(n)$。
• 由于常数过大，会导致 TLE。

空间复杂度

• 需要 $O(n)$ 的额外空间记录状态。

C++ 代码

class Solution {
public:
    int minCost(string s, vector<int>& cost) {
        const int n = s.size(), m = 26;
        vector<vector<int>> f(n+1, vector<int>(m, INT_MAX));

        for (int j = 0; j < m; j++)
            f[0][j] = 0;

        for (int i = 1; i <= n; i++)
            for (int j = 0; j < m; j++) {
                f[i][j] = min(f[i][j], f[i-1][j] + cost[i-1]);

                int k = s[i-1] - 'a';
                if (j != k)
                    f[i][k] = min(f[i][k], f[i-1][j]);
            }

        int ans = INT_MAX;
        for (int j = 0; j < m; j++)
            ans = min(ans, f[n][j]);

        return ans;
    }
};

算法2

(前缀和) $O(n)$

1. 我们只需要将每一段连续出现的字符删除到只剩 1 个。
2. 维护遍历 sum 和 m，分别表示当前连续字符的总代价，以及其中最大的代价。
3. 删除连续的一段时，需要保留代价最大的，故答案累加 sum - m。

时间复杂度

• 遍历数组一次，时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int minCost(string s, vector<int>& cost) {
        const int n = s.size();
        int ans = 0;
        int sum = 0, m = 0;

        for (int i = 0; i < n; i++) {
            if (i == 0 || s[i] != s[i-1]) {
                ans += sum - m;
                sum = m = cost[i];
            } else {
                sum += cost[i];
                m = max(m, cost[i]);
            }
        }

        ans += sum - m;
        return ans;
    }
};