greedy October 3, 2022

Minimum time to make rope colorful

Time O(n) Space O(1) Open original problem

For a group of continuous same characters, we need to delete all the group but leave only one character. For each group of continuous same characters, we need cost = sum_cost(group) - max_cost(group).

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

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