Minimum Deletion Cost to Avoid Repeating Letters

Moderate
0/80
profile
Contributed by
13 upvotes
Asked in companies
AppleMicrosoftTesla

Problem statement

Ninja has given a string 'S' of lowercase characters of size 'N'. He also has provided an array 'COST' where 'COST[i]' refers to the Cost of deleting the ‘i’th character in the string.

Ninja doesn't like a string with the same adjacent characters, so he asked you to help him transform the given string into the string with no adjacent repetitive characters by deleting some characters in it.

Cost of deleting some characters is the sum of costs of individual deletion of characters at every position. Your task is to find the minimum cost needed to transform the string with no adjacent repetitive characters.

Example: 
Input: 'S' = "babbc", 'COST' = [1, 2, 3, 4, 5] 
Output: 3

By deleting the third letter 'b' with cost, 3 will transform the string into 'babc'. This is the minimum possible cost to transform the string.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer 'T', denoting the number of test cases. 

For each test case, the first line contains an integer 'N' second line contains a string of size 'N' and the last line contains the 'N' elements in the array 'COST'.
Output format : 
For each test case, print the minimum cost needed to transform the string.

Output for each test case will be printed in a separate line.
Note : 
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= ‘T’ <= 10
2 <= 'N' <= 10^4
1 <= 'COST[i]'<= 10^4
Time Limit: 1sec
Sample Input 1 :
2
5
abaac
1 2 3 4 5
4
abcd
4 5 3 4
Sample Output 1 :
3
0
Explanation Of Sample Input 1 :
For the first test case, By deleting the third letter 'a' with cost, 3 will transform the string into ‘abac’. This is the minimum possible cost to transform the string.

For the second test case, all adjacent characters in the string are already unequal. Hence the cost will be 0.
Sample Input 2 :
2
6
pqrrss
7 2 3 4 5 6
4
xyyz
1 3 7 5
Sample Output 2 :
8
3
Hint

Try to think how we can vanish a group of the same continuous characters with less cost.

Approaches (1)
Greedy Solution

Approach:  The main observation is For a group of the same continuous characters, we need to delete all the groups but leave only one character.

We will pick the character with the maximum cost in the group to leave and then delete the rest of them.

 

Algorithm : 

  1. Initialize a variable 'answer', 'maximumCost' and 'costSum' with 0.
  2. Run a loop from 0 to 'N' with iterating variable 'I'
    • If 'I' >0 and 'S[I]' is not equal to the 'S[I - 1'] then add 'costSum - maximumCost' to the 'answer' and update both 'costSum' and 'maximumCost' with 0.
    • Add 'COST[I]' to 'costSum'.
    • Update 'maximumCost' with maximum of 'maximumCost' and 'COST[I]'
  3. Add 'costSum - maximumCost' to the 'answer'
  4. Return 'answer'
Time Complexity

O(N), where 'N' is the size of the input string.

 

As we are iterating over the whole string of size 'N' the time complexity will be O(N)

Space Complexity

O(1)
 

As we are using the constant extra space, the space complexity will be O(1)

Code Solution
(100% EXP penalty)
Minimum Deletion Cost to Avoid Repeating Letters
Full screen
Console