Minimum Time to Make Rope Colorful

main.md

Question

Approach

I sweep the string left to right and treat each run of consecutive same-colored balloons as a group. To avoid adjacent equal colors I must remove all but one balloon in each group; the minimum cost for a group is the sum of its removal times minus the maximum time in that group. Equivalently, while scanning, whenever the current balloon has the same color as the previous one, I remove the cheaper of the two (add min(prev_time, cur_time) to the answer) and keep the larger time as the survivor for further comparisons.

Implementation

class Solution:
    def minCost(self, colors: str, neededTime: List[int]) -> int:
        total = 0
        prev_time = neededTime[0]
        for i in range(1, len(colors)):
            if colors[i] == colors[i-1]:
                total += min(prev_time, neededTime[i])
                prev_time = max(prev_time, neededTime[i])
            else:
                prev_time = neededTime[i]
        return total

Complexities

• Time: O(n)
• Space: O(1)