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 :
- Initialize
res
,max_cost
,sum_cost
andprev
- Iterate through the string and cost list
- If the current character is the same as the previous character, add the current cost to
sum_cost
and updatemax_cost
- If it's a different character, subtract
max_cost
fromsum_cost
and add it to the resultres
and then updatemax_cost
,sum_cost
, andprev
- Repeat steps 3 and 4 until you've processed all characters in the string
- Add the remaining
sum_cost - max_cost
to theres
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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.