# Minimum Time to Make Rope Colorful
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-time-to-make-rope-colorful)
Canonical: https://scaleengineer.com/dsa/problems/minimum-time-to-make-rope-colorful
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array, String
---
## Problem
Alice has `n` balloons arranged on a rope. You are given a **0-indexed** string `colors` where `colors[i]` is the color of the `ith` 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 `ith` balloon from the rope.

Return _the **minimum time** Bob needs to make the rope **colorful**_.

**Example 1:**

![](https://assets.glich.co/dsa/minimum-time-to-make-rope-colorful/image0.jpg) 

**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:**

![](https://assets.glich.co/dsa/minimum-time-to-make-rope-colorful/image1.jpg) 

**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:**

![](https://assets.glich.co/dsa/minimum-time-to-make-rope-colorful/image2.jpg) 

**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.

# Approaches
## Grouping Consecutive Colors
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.
**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.
**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.
### Explanation
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`.

```java
class Solution {
    public int minCost(String colors, int[] neededTime) {
        int n = colors.length();
        int totalTime = 0;
        int i = 0;
        while (i < n) {
            int j = i + 1;
            while (j < n && colors.charAt(j) == colors.charAt(i)) {
                j++;
            }
            // A group of same-colored balloons is from index i to j-1
            if (j - i > 1) {
                int sumCost = 0;
                int maxCost = 0;
                for (int k = i; k < j; k++) {
                    sumCost += neededTime[k];
                    maxCost = Math.max(maxCost, neededTime[k]);
                }
                totalTime += (sumCost - maxCost);
            }
            i = j;
        }
        return totalTime;
    }
}
```
### Algorithm
1. Initialize `totalTime = 0` and a pointer `i = 0`.
2. Use a `while` loop to iterate as long as `i` is less than the number of balloons `n`.
3. Inside the loop, start a second pointer `j = i + 1` to find the end of the current group of same-colored balloons.
4. Advance `j` as long as `j < n` and `colors.charAt(j) == colors.charAt(i)`.
5. After the inner loop, the indices from `i` to `j-1` form a group of identical colors.
6. If this group contains more than one balloon (i.e., `j - i > 1`), calculate the cost to make it colorful.
7. 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.
8. The cost for this group is `sumCost - maxCost`. Add this to `totalTime`.
9. Move the main pointer `i` to `j` to start processing the next group.
10. After the main loop finishes, return `totalTime`.

## Optimized Single Pass
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    public int minCost(String colors, int[] neededTime) {
        int totalTime = 0;
        int n = colors.length();
        int sumCostInGroup = 0;
        int maxCostInGroup = 0;

        for (int i = 0; i < n; i++) {
            // If the color changes or it's the first balloon, a group might have ended.
            if (i > 0 && colors.charAt(i) != colors.charAt(i - 1)) {
                // Add the cost of the previous group to the total.
                totalTime += sumCostInGroup - maxCostInGroup;
                // Reset for the new group.
                sumCostInGroup = 0;
                maxCostInGroup = 0;
            }
            // Add current balloon's cost to the current group's sum.
            sumCostInGroup += neededTime[i];
            // Update the max cost in the current group.
            maxCostInGroup = Math.max(maxCostInGroup, neededTime[i]);
        }

        // Account for the last group of colors.
        totalTime += sumCostInGroup - maxCostInGroup;

        return totalTime;
    }
}
```
### Algorithm
1. Initialize `totalTime = 0`, `sumCostInGroup = 0`, and `maxCostInGroup = 0`.
2. Iterate through the balloons with a pointer `i` from `0` to `n-1`.
3. 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]`).
4. 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`.
5. After adding the cost, reset `sumCostInGroup` and `maxCostInGroup` to `0` to start fresh for the new group.
6. For every balloon, update the current group's statistics: add `neededTime[i]` to `sumCostInGroup` and update `maxCostInGroup = max(maxCostInGroup, neededTime[i])`.
7. 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`.
8. Return `totalTime`.

# Solutions
### Java

```java
class Solution {
public
  int minCost(String colors, int[] neededTime) {
    int ans = 0;
    int n = neededTime.length;
    for (int i = 0, j = 0; i < n; i = j) {
      j = i;
      int s = 0, mx = 0;
      while (j < n && colors.charAt(j) == colors.charAt(i)) {
        s += neededTime[j];
        mx = Math.max(mx, neededTime[j]);
        ++j;
      }
      if (j - i > 1) {
        ans += s - mx;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minCost(string colors, vector<int> &neededTime) {
    int ans = 0;
    int n = colors.size();
    for (int i = 0, j = 0; i < n; i = j) {
      j = i;
      int s = 0, mx = 0;
      while (j < n && colors[j] == colors[i]) {
        s += neededTime[j];
        mx = max(mx, neededTime[j]);
        ++j;
      }
      if (j - i > 1) {
        ans += s - mx;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    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

```