Minimum Time to Make Rope Colorful — LeetCode 1578 Python Solution
MediumGreedyArrayStringDynamic Programming
- Problem
- #1578
- Pattern
- Greedy
- Reading time
- 3 min
- Source
- leetcode.com
The 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.
Example
- 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.
Python solution
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 ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(1), where n is the number of balloons auxiliary |
Pattern: Greedy
Take the locally best option every time — when you can prove that never costs you later. LeetCode 1578. Minimum Time to Make Rope Colorful is filed here because LeetCode tags it Greedy, which is the vocabulary this hub collects.
The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 1578. Minimum Time to Make Rope Colorful?
- LeetCode 1578. Minimum Time to Make Rope Colorful is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1578. Minimum Time to Make Rope Colorful?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 1578. Minimum Time to Make Rope Colorful?
- The Python solution on this page uses O(1), where n is the number of balloons auxiliary space.
- What topics does LeetCode 1578. Minimum Time to Make Rope Colorful cover?
- LeetCode 1578. Minimum Time to Make Rope Colorful is tagged Greedy, Array, String and Dynamic Programming on LeetCode.