Leetcode 1578. Minimum Deletion Cost to Avoid Repeating Letters

Problem Explanation

The problem requires us to return the minimum cost of deletions from a list of characters such that there are no two identical letters next to each other, considering each character deletion at a specific index incurs a defined cost. All deletions take place simultaneously, and the cost of deleting characters does not change once a deletion occurs.

The goal is to minimize the cost of deletions. So, in each continuous group of the same character, we delete all occurrences of the character, except the one with the maximum cost.

Let's illustrate the approach using an example: For example, if

1
2
3s = "aabaa", cost = [1,2,3,4,1], 

In the continuous group "aa", we delete 'a' with cost 1, and keep 'a' with the cost 2. Then we come to 'b', which is alone, so we keep it. Next, in the continuous group "aa", we delete 'a' with cost 1, and keep 'a' with cost 4. Thus, the total cost of deletion is 1 + 1 = 2.

Python Solution

1
2python
3class Solution:
4    def minCost(self, s: str, cost: List[int]) -> int:
5        res, max_cost, sum_cost, prev  = 0, 0, 0, s[0]
6        for i in range(len(s)):
7            if s[i] == prev:
8                sum_cost += cost[i]
9                max_cost = max(max_cost, cost[i])
10            else:
11                res += sum_cost - max_cost
12                max_cost, sum_cost, prev = cost[i], cost[i], s[i]
13        res += sum_cost - max_cost
14        return res

In the Python solution, we iterate through the character list and cost list at the same time. If the current character is the same as the previous one, we add the current cost to sum_cost and update max_cost if the current cost is higher. If it's a different character, we subtract the max_cost from sum_cost and add it to the result res. We then update max_cost, sum_cost and prev for the new character. At the end of the iteration, we need to add the remaining sum_cost - max_cost to res to account for the last group of characters.

C# Solution

1
2csharp
3public class Solution {
4    public int MinCost(string s, int[] cost) {
5        int res = 0, max_cost = 0, sum_cost = 0;
6        char prev = s[0];
7        for(int i=0; i<s.Length; i++){
8            if (s[i] == prev){
9                sum_cost += cost[i];
10                max_cost = Math.Max(max_cost, cost[i]);
11            }
12            else{
13                res += sum_cost - max_cost;
14                max_cost = cost[i];
15                sum_cost = cost[i];
16                prev = s[i];
17            }
18        }
19        res += sum_cost - max_cost;
20        return res;
21    }
22}

The C# solution uses the same approach as the Python solution.

Java Solution

1
2java
3class Solution {
4    public int minCost(String s, int[] cost) {
5        int res = 0, max_cost = 0, sum_cost = 0;
6        char prev = s.charAt(0);
7        for(int i=0; i<s.length(); i++){
8            if (s.charAt(i) == prev){
9                sum_cost += cost[i];
10                max_cost = Math.max(max_cost, cost[i]);
11            }
12            else{
13                res += sum_cost - max_cost;
14                max_cost = cost[i];
15                sum_cost = cost[i];
16                prev = s.charAt(i);
17            }
18        }
19        res += sum_cost - max_cost;
20        return res;
21    }
22}

The Java solution uses the same approach as the Python and C# solution.

Javascript Solution

1
2javascript
3var minCost = function(s, cost) {
4    let res = 0, max_cost = 0, sum_cost = 0, prev = s[0];
5    for(let i=0; i<s.length; i++){
6        if (s[i] == prev){
7            sum_cost += cost[i];
8            max_cost = Math.max(max_cost, cost[i]);
9        }
10        else{
11            res += sum_cost - max_cost;
12            max_cost = cost[i];
13            sum_cost = cost[i];
14            prev = s[i];
15        }
16    }
17    res += sum_cost - max_cost;
18    return res;
19};

The Javascript solution uses the same approach as the Python, C# and Java solution.

C++ Solution

1
2cpp
3class Solution {
4public:
5    int minCost(string s, vector<int>& cost) {
6        int res = 0, max_cost = cost[0], sum_cost = cost[0];
7        for(int i=1; i<s.size(); i++){
8            if (s[i] == s[i-1]){
9                sum_cost += cost[i];
10                max_cost = max(max_cost, cost[i]);
11            }
12            else{
13                res += sum_cost - max_cost;
14                max_cost = cost[i];
15                sum_cost = cost[i];
16            }
17        }
18        res += sum_cost - max_cost;
19        return res;
20    }
21};

The C++ solution uses the same approach as the Python, C#, Java and Javascript solution.So to summarize the algorithm :

1. Initialize res, max_cost, sum_cost and prev
2. Iterate through the string and cost list
3. If the current character is the same as the previous character, add the current cost to sum_cost and update max_cost
4. If it's a different character, subtract max_cost from sum_cost and add it to the result res and then update max_cost, sum_cost, and prev
5. Repeat steps 3 and 4 until you've processed all characters in the string
6. Add the remaining sum_cost - max_cost to the res to account for the last group of characters.

This approach ensures that we are removing characters with the smallest possible cost first to minimize the total cost of deletions. The solutions based on this approach in Python, C#, Java, Javascript and C++ all provide an efficient and effective way to solve the problem.

By carefully managing the amount of information stored and processing steps taken, this solution avoids doing unnecessary work and achieves good performance.