Minimum Time to Make Rope Colorful

Problem Statement

Alice owns a series of n balloons arranged sequentially on a rope, each colored and denoted by a string colors where colors[i] represents the color of the i-th balloon. To add vibrant variability, Alice wants no two adjacent balloons to share the same color. To help achieve this, Bob steps in with the ability to remove balloons at a specific time cost for each balloon, detailed in the integer array neededTime where neededTime[i] represents the seconds required to remove the i-th balloon.

The challenge lies in determining the minimum total time Bob needs to spend to ensure that no two consecutive balloons have the same color, thus making the rope "colorful." This involves strategically removing some balloons while minimizing the total time taken.

Examples

Example 1

Input:

colors = "abaac", neededTime = [1,2,3,4,5]

Output:

3

Explanation:

In the above image, 'a' is blue, 'b' is red, and 'c' is green.
Bob can remove the blue balloon at index 2. This takes 3 seconds.
There are no longer two consecutive balloons of the same color. Total time = 3.

Example 2

Input:

colors = "abc", neededTime = [1,2,3]

Output:

0

Explanation:

The rope is already colorful. Bob does not need to remove any balloons from the rope.

Example 3

Input:

colors = "aabaa", neededTime = [1,2,3,4,1]

Output:

2

Explanation:

Bob will remove the balloons at indices 0 and 4. Each balloons takes 1 second to remove.
There are no longer two consecutive balloons of the same color. Total time = 1 + 1 = 2.

Constraints

• n == colors.length == neededTime.length
• 1 <= n <= 105
• 1 <= neededTime[i] <= 104
• colors contains only lowercase English letters.

Approach and Intuition

The goal here is to ensure that no two consecutive balloons are of the same color, minimizing the time taken by Bob to remove necessary balloons. The approach revolves around assessing groups of consecutive balloons of the same color and deciding which balloons to remove to minimize the time:

1. Traverse through the string colors and identify clusters of balloons where consecutive balloons share the same color.
2. For each cluster:
   • If only one balloon exists within this cluster, no action is required.
   • If multiple balloons exist, determine which balloon(s) to remove. The most time-efficient strategy generally involves keeping the balloon with the maximum neededTime and removing the others. This way, the sum of the neededTime values of the removed balloons (which are smaller) will be minimized.
3. Accumulate the neededTime values of all removed balloons throughout the traversal to compute the total minimum time needed.

For example, consider a scenario where the colors array represents several clusters of the same colored balloons (e.g., "aabbbcca"). For the "aa" cluster, you would choose to keep the balloon that costs more time to remove and remove the other to save on the overall time. Continue this approach throughout the string.

Through this efficient handling of clusters of balloons, Bob can ensure the sequence is made colorful with a minimized time cost.

Solutions

class Solution {
public:
    int minimumCost(string s, vector<int>& timeRequired) {
        int summedCost = 0, maxTimeInGroup = 0;
            
        for (int j = 0; j < s.length(); ++j) {
            if (j > 0 && s[j] != s[j - 1]) {
                maxTimeInGroup = 0;
            }
                
            summedCost += min(maxTimeInGroup, timeRequired[j]);
            maxTimeInGroup = max(maxTimeInGroup, timeRequired[j]);
        }
            
        return summedCost;
    }
};