Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1578.html
1578. Minimum Deletion Cost to Avoid Repeating Letters (Medium)
Given a string s
and an array of integers cost
where cost[i]
is the cost of deleting the character i
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.
Related Topics:
Greedy
Solution 1.
We traverse the string from left to right. For each substring that contains the same characters, we calculate the sum
of the costs and the maximum cost mx
. We add sum  mx
to the answer.

// OJ: https://leetcode.com/problems/minimumdeletioncosttoavoidrepeatingletters/ // Time: O(N) // Space: O(1) class Solution { public: int minCost(string s, vector<int>& cost) { int i = 0, N = s.size(), ans = 0; while (i < N) { int j = i, sum = 0, mx = 1; for (; i < N && s[i] == s[j]; ++i) sum += cost[i], mx = max(mx, cost[i]); ans += sum  mx; } return ans; } };

class Solution { public int minCost(String s, int[] cost) { int totalCost = 0; char prev = s.charAt(0); int maxCost = cost[0]; int curTotalCost = cost[0]; int length = s.length(); for (int i = 1; i < length; i++) { char c = s.charAt(i); int curCost = cost[i]; if (c == prev) { maxCost = Math.max(maxCost, curCost); curTotalCost += curCost; } else { totalCost += curTotalCost  maxCost; prev = c; maxCost = curCost; curTotalCost = curCost; } } totalCost += curTotalCost  maxCost; return totalCost; } }

print("Todo!")
Solution 2.
// OJ: https://leetcode.com/problems/minimumdeletioncosttoavoidrepeatingletters/
// Time: O(N)
// Space: O(1)
class Solution {
public:
int minCost(string s, vector<int>& cost) {
int N = s.size(), ans = 0;
for (int i = 0; i + 1 < N; ++i) {
if (s[i] != s[i + 1]) continue;
if (cost[i] > cost[i + 1]) swap(cost[i], cost[i + 1]);
ans += cost[i];
}
return ans;
}
};