Problem Statement in English

You’re given a rope represented by a string colors, where each character represents the color of a segment of the rope. You are also given an array neededTime where neededTime[i] is the time required to remove the i-th segment of the rope.

The goal is to make the rope colorful, meaning no two adjacent segments should have the same color, by removing segments with the minimum total time.

Approach

The idea is to iterate through the string and whenever we find a sequence of adjacent segments with the same color, we calculate the total time required to remove all but the most expensive segment in that sequence. This can be done by maintaining a running sum of the times and keeping track of the maximum time in that sequence.

When we encounter a different color, we add the difference between the total time and the maximum time to our result, as that represents the minimum time needed to make that part of the rope colorful.

Solution in Python


class Solution:
    def minCost(self, colors: str, neededTime: List[int]) -> int:
        res = l = 0
        colors += "!"

        for r in range(len(colors)):
            windowSum = windowMax = 0
            
            while colors[l] != colors[r]:
                windowMax = max(windowMax, neededTime[l])
                windowSum += neededTime[l]
                l += 1
            
            res += windowSum - windowMax

        return res

Complexity

  • Time: $O(n)$
    Since we are iterating through the string once.

  • Space: $O(1)$
    We are using a constant amount of space for the variables.

And we are done.