题目描述

给你一个字符串 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 中只含有小写英文字母

算法分析

当枚举到当前字符s[i]时，通过j指针可以找出从i位置字符是s[i]的区间[i , j - 1]

• 1、若想达到任意相邻两个字母不相同，即需要从[i, j - 1]区间中，只能存活一个s[i]字符，
• 2、若想删除该字符的成本最少，即只能存活一个s[i]字符，其中该字符的cost[i]最大，假设最大是max，等价于删除该字符的花费的成本最小sum - max，其中sum是s[i, j -1]的花费总和

时间复杂度 $O(n)$

Java 代码

class Solution {
    public int minCost(String s, int[] cost) {
        int n = s.length();
        int res = 0;
        for(int i = 0;i < s.length();i ++)
        {
            char c = s.charAt(i);
            int sum = 0, maxv = 0;
            int j = i;
            while(j < n && s.charAt(j) == c) 
            {
                sum += cost[j];
                maxv = Math.max(maxv, cost[j]);
                j ++;
            }
            if(j - i >= 1) res += sum - maxv;
            i = j - 1;
        }
        return res;
    }
}