原文链接: https://leetcode-cn.com/problems/minimum-deletion-cost-to-avoid-repeating-letters

英文原文

Given a string s and an array of integers cost where cost[i] is the cost of deleting the ith character in s.

Return the minimum cost of deletions such that there are no two identical letters next to each other.

Notice that you will delete the chosen characters at the same time, in other words, after deleting a character, the costs of deleting other characters will not change.

 

Example 1:

Input: s = "abaac", cost = [1,2,3,4,5]
Output: 3
Explanation: Delete the letter "a" with cost 3 to get "abac" (String without two identical letters next to each other).

Example 2:

Input: s = "abc", cost = [1,2,3]
Output: 0
Explanation: You don't need to delete any character because there are no identical letters next to each other.

Example 3:

Input: s = "aabaa", cost = [1,2,3,4,1]
Output: 2
Explanation: Delete the first and the last character, getting the string ("aba").

 

Constraints:

• s.length == cost.length
• 1 <= s.length, cost.length <= 10^5
• 1 <= cost[i] <= 10^4
• s contains only lowercase English letters.

中文题目

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

通过代码

高赞题解

解题思路

遍历，找到相同的字母，取成本小的，并将没有消费的成本放在下一次比较的字符成本中。

代码

class Solution {
public:
    int minCost(string s, vector<int>& cost) {
        int n = s.size();
        int sum = 0;
        for(int i = 0;i<n-1;i++)
        {
            if(s[i] == s[i+1])
            {
                sum+= min(cost[i],cost[i+1]); 
                if(cost[i]>cost[i+1])swap(cost[i],cost[i+1]);
            }
        }
        return sum;
    }
};

统计信息

通过次数	提交次数	AC比率
11277	19307	58.4%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言