Minimum Time to Make Rope Colorful

Med

#1452Time: O(N) - Although there are nested loops, each balloon is visited a constant number of times. The outer pointer `i` and the inner pointer `j` both traverse the array from left to right only once.Space: O(1) - We only use a few variables for pointers and costs, so the space required is constant.

Patterns

Dynamic Programming Greedy

Data structures

Array String

Prompt

Alice has n balloons arranged on a rope. You are given a 0-indexed string colors where colors[i] is the color of the i^th balloon.

Alice wants the rope to be colorful. She does not want two consecutive balloons to be of the same color, so she asks Bob for help. Bob can remove some balloons from the rope to make it colorful. You are given a 0-indexed integer array neededTime where neededTime[i] is the time (in seconds) that Bob needs to remove the i^th balloon from the rope.

Return the minimum time Bob needs to make the rope colorful.

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 <= 10⁵
1 <= neededTime[i] <= 10⁴
colors contains only lowercase English letters.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach iterates through the balloons and identifies contiguous groups of balloons with the same color. For each group, to make the rope colorful, we must remove all but one balloon. To minimize the removal time, we should keep the balloon that is most expensive to remove and remove all others in that group. The total minimum time is the sum of costs for each such group.

Algorithm

Initialize totalTime = 0 and a pointer i = 0.
Use a while loop to iterate as long as i is less than the number of balloons n.
Inside the loop, start a second pointer j = i + 1 to find the end of the current group of same-colored balloons.
Advance j as long as j < n and colors.charAt(j) == colors.charAt(i).
After the inner loop, the indices from i to j-1 form a group of identical colors.
If this group contains more than one balloon (i.e., j - i > 1), calculate the cost to make it colorful.
To do this, iterate from k = i to j-1, calculating the sumCost of all neededTime in the group and finding the maxCost within the group.
The cost for this group is sumCost - maxCost. Add this to totalTime.
Move the main pointer i to j to start processing the next group.
After the main loop finishes, return totalTime.

Walkthrough

We can solve this problem by iterating through the rope and processing it in chunks of same-colored balloons. We use a main pointer, i, to mark the beginning of a potential group.

From i, we use a second pointer, j, to find the end of the contiguous block of balloons that share the same color as the one at i. Once j stops, we have identified a group from index i to j-1.

If this group has only one balloon (j - i == 1), it doesn't violate the colorful condition, so we do nothing. If the group is larger, we must remove all but one balloon. The greedy choice to minimize the time is to keep the balloon that takes the most time to remove (maxCost) and remove all others. The total time for removing the others is equivalent to the sum of all removal times in the group (sumCost) minus the one we keep (maxCost).

We add this value (sumCost - maxCost) to our running total. Then, we continue our search for the next group by setting i = j.

1class Solution {2    public int minCost(String colors, int[] neededTime) {3        int n = colors.length();4        int totalTime = 0;5        int i = 0;6        while (i < n) {7            int j = i + 1;8            while (j < n && colors.charAt(j) == colors.charAt(i)) {9                j++;10            }11            // A group of same-colored balloons is from index i to j-112            if (j - i > 1) {13                int sumCost = 0;14                int maxCost = 0;15                for (int k = i; k < j; k++) {16                    sumCost += neededTime[k];17                    maxCost = Math.max(maxCost, neededTime[k]);18                }19                totalTime += (sumCost - maxCost);20            }21            i = j;22        }23        return totalTime;24    }25}

Complexity

Time

O(N) - Although there are nested loops, each balloon is visited a constant number of times. The outer pointer `i` and the inner pointer `j` both traverse the array from left to right only once.

Space

O(1) - We only use a few variables for pointers and costs, so the space required is constant.

Trade-offs

Pros

The logic is very intuitive and directly follows the problem statement of resolving conflicts in groups.
It is efficient with optimal time and space complexity.

Cons

The use of nested loops might initially seem like it has a higher time complexity (e.g., O(N^2)) if not analyzed carefully, which can be misleading.

This approach refines the grouping method by using a single loop and a few state variables to track the current group of same-colored balloons. It calculates the cost on the fly as it transitions from one group to the next, avoiding nested loops and making the implementation more streamlined.

Algorithm

Initialize totalTime = 0, sumCostInGroup = 0, and maxCostInGroup = 0.
Iterate through the balloons with a pointer i from 0 to n-1.
Check if the current balloon starts a new color group. This happens if it's the first balloon (i == 0) or if its color is different from the previous one (colors[i] != colors[i-1]).
If a new group starts (and it's not the very first balloon), it means the previous group has just ended. Calculate the cost for the previous group by sumCostInGroup - maxCostInGroup and add it to totalTime.
After adding the cost, reset sumCostInGroup and maxCostInGroup to 0 to start fresh for the new group.
For every balloon, update the current group's statistics: add neededTime[i] to sumCostInGroup and update maxCostInGroup = max(maxCostInGroup, neededTime[i]).
After the loop finishes, the last group's cost has not been added to totalTime yet. Calculate and add the cost for this final group: totalTime += sumCostInGroup - maxCostInGroup.
Return totalTime.

Walkthrough

The core greedy strategy remains the same: for any group of consecutive identical balloons, we keep the one with the maximum removal time and remove the rest. The cost for the group is sum_of_times - max_time.

This can be implemented elegantly in a single pass. We iterate through the balloons while maintaining the sumCostInGroup and maxCostInGroup for the current contiguous block of same-colored balloons.

As we iterate, if we encounter a balloon that has a different color from the previous one, it signifies the end of the previous group. At this point, we calculate the cost for the just-completed group (sumCostInGroup - maxCostInGroup) and add it to our totalTime. We then reset the state variables (sumCostInGroup and maxCostInGroup) to begin accumulating stats for the new group.

If the current balloon has the same color as the previous one, we are still in the same group, so we just update the running sum and maximum for the current group.

A final calculation is needed after the loop terminates to account for the very last group of balloons, as there is no subsequent color change to trigger its calculation within the loop.

1class Solution {2    public int minCost(String colors, int[] neededTime) {3        int totalTime = 0;4        int n = colors.length();5        int sumCostInGroup = 0;6        int maxCostInGroup = 0;7 8        for (int i = 0; i < n; i++) {9            // If the color changes or it's the first balloon, a group might have ended.10            if (i > 0 && colors.charAt(i) != colors.charAt(i - 1)) {11                // Add the cost of the previous group to the total.12                totalTime += sumCostInGroup - maxCostInGroup;13                // Reset for the new group.14                sumCostInGroup = 0;15                maxCostInGroup = 0;16            }17            // Add current balloon's cost to the current group's sum.18            sumCostInGroup += neededTime[i];19            // Update the max cost in the current group.20            maxCostInGroup = Math.max(maxCostInGroup, neededTime[i]);21        }22 23        // Account for the last group of colors.24        totalTime += sumCostInGroup - maxCostInGroup;25 26        return totalTime;27    }28}

Complexity

Time

O(N) - We iterate through the array of balloons exactly once.

Space

O(1) - We only use a few variables to store the running total and group statistics, requiring constant extra space.

Trade-offs

Pros

Highly efficient with optimal O(N) time and O(1) space complexity.
Elegant implementation with a single pass through the data.
Does not modify the input array.

Cons

The logic to handle the state transition between groups and the special case for the last group after the loop can be slightly tricky to get right.

Solutions

Solution

1class Solution {2public3  int minCost(String colors, int[] neededTime) {4    int ans = 0;5    int n = neededTime.length;6    for (int i = 0, j = 0; i < n; i = j) {7      j = i;8      int s = 0, mx = 0;9      while (j < n && colors.charAt(j) == colors.charAt(i)) {10        s += neededTime[j];11        mx = Math.max(mx, neededTime[j]);12        ++j;13      }14      if (j - i > 1) {15        ans += s - mx;16      }17    }18    return ans;19  }20}

1class Solution {2public:3  int minCost(string colors, vector<int> &neededTime) {4    int ans = 0;5    int n = colors.size();6    for (int i = 0, j = 0; i < n; i = j) {7      j = i;8      int s = 0, mx = 0;9      while (j < n && colors[j] == colors[i]) {10        s += neededTime[j];11        mx = max(mx, neededTime[j]);12        ++j;13      }14      if (j - i > 1) {15        ans += s - mx;16      }17    }18    return ans;19  }20};

1class Solution:2    def minCost(self, colors: str, neededTime: List[int]) -> int: ans = i = 0 n = len(colors) while i < n: j = i s = mx = 0 while j < n and colors[j] == colors[i]: s += neededTime[j] if mx < neededTime[j]: mx = neededTime[j] j += 1 if j - i > 1: ans += s - mx i = j return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem