Search

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.

Solution:

class Solution {
    public int minCost(String s, int[] cost) {
        int mincost=0;
        for(int i=1;i<s.length();i++)
        {
           if(s.charAt(i)==s.charAt(i-1))
            {
                if(cost[i-1]<cost[i])
                {
                   mincost+=cost[i-1];
                }
                    
                else
                {
                    mincost+=cost[i];
                    cost[i]=cost[i-1];
                }  
            } 
        }
        return mincost;
    }
}

233 views0 comments

Recent Posts

See All

A string s is called good if there are no two different characters in s that have the same frequency. Given a string s, return the minimum number of characters you need to delete to make s good. The f

The numeric value of a lowercase character is defined as its position (1-indexed) in the alphabet, so the numeric value of a is 1, the numeric value of b is 2, the numeric value of c is 3, and so on.