5509. 避免重复字母的最小删除成本 [medium]
5509. 避免重复字母的最小删除成本 [medium]
给你一个字符串 s 和一个整数数组 cost ，其中 cost[i] 是从 s 中删除字符 i 的代价。
返回使字符串任意相邻两个字母不相同的最小删除成本。
请注意，删除一个字符后，删除其他字符的成本不会改变。
示例 1：
输入：s = "abaac", cost = [1,2,3,4,5]
输出：3
解释：删除字母 "a" 的成本为 3，然后得到 "abac"（字符串中相邻两个字母不相同）。
示例 2：
输入：s = "abc", cost = [1,2,3]
输出：0
解释：无需删除任何字母，因为字符串中不存在相邻两个字母相同的情况。
示例 3：
输入：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 中只含有小写英文字母
First Try
周赛题目，其实跟第一题5507有点相关，也是相邻重复，而非整个数组不存在重复字符。
既然是消除相邻重复，那么每个字符只需要往后考虑，把所有重复的删除掉，下一个从非重复开始的字符就不需要考虑前面的情况了。删除重复的过程中，只需要选择最小权重值的即可。
我这边写得比较渐进式了，删除的时候还需要逐字符考虑和跳进，其实可以一次性统计所有后面重复的数组，然后选择权重最大的保留下来即可。
算起来这是周赛中很少见的如此简单的第三题了。
class Solution:
def minCost(self, s: str, cost: List[int]) -> int:
# 这不就贪心算法一波带走？
# 只需往后面考虑，前面自动处理后面的
count = 0
idx = 0
while idx < len(s):
pre_idx = idx
after_idx = pre_idx + 1
while after_idx < len(s) and s[after_idx] == s[pre_idx]:
count += min([cost[pre_idx], cost[after_idx]])
if cost[pre_idx] >= cost[after_idx]:
after_idx += 1
else:
pre_idx, after_idx = after_idx, after_idx + 1
idx = after_idx
return count