Minimum Time to Make Rope Colorful — Problem & Solution
Minimum Time to Make Rope Colorful solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Minimum Time to Make Rope Colorful is a medium coding problem on arrays, strings and dynamic programming, asked in Amazon and Adobe interviews.
- Difficulty: Medium
- Topics: Arrays, Strings, Dynamic Programming, Greedy
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Alice has n balloons on a rope; colors[i] is the colour of the i-th balloon. The rope is colorful if no two consecutive balloons share a colour.
Bob can remove the i-th balloon at a cost of neededTime[i] seconds. Return the minimum total time needed to make the rope colorful.
Example 1
Input: colors = "abaac", neededTime = [1,2,3,4,5]
Output: 3
Explanation: Remove the cheaper of the two consecutive a's.
Example 2
Input: colors = "abc", neededTime = [1,2,3]
Output: 0
Example 3
Input: colors = "aabaa", neededTime = [1,2,3,4,1]
Output: 2
Constraints
1 <= colors.length <= 40neededTime.length == colors.length1 <= neededTime[i] <= 10000colors consists of lowercase English letters.
Hints for Minimum Time to Make Rope Colorful
Hint 1
Balloons only conflict inside a run of one colour, and each run must be reduced to a single balloon.
Hint 2
Within a run, keep the most expensive balloon and remove the rest.
Hint 3
So each run contributes
sum(run) - max(run).
How to solve Minimum Time to Make Rope Colorful
Balloons only conflict within a run of one colour, and each run must shrink to a single balloon — keep the most expensive one.
Approach
- Scan runs of equal colour.
- For each run add
sum(times) - max(times).
Why it works
Runs are independent, and within a run removing all but the costliest balloon is the cheapest way to leave exactly one.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- The equivalent single-pass form keeps a running max per run and adds the smaller of each adjacent equal pair.
Reference solution
Python
def minCost(colors: str, neededTime) -> int:
total = 0
i = 0
while i < len(colors):
j = i
run_sum = 0
run_max = 0
while j < len(colors) and colors[j] == colors[i]:
run_sum += neededTime[j]
run_max = max(run_max, neededTime[j])
j += 1
total += run_sum - run_max
i = j
return totalJava
public static int minCost(String colors, int[] neededTime) {
int total = 0, i = 0;
while (i < colors.length()) {
int j = i, sum = 0, maxT = 0;
while (j < colors.length() && colors.charAt(j) == colors.charAt(i)) {
sum += neededTime[j];
maxT = Math.max(maxT, neededTime[j]);
j++;
}
total += sum - maxT;
i = j;
}
return total;
}C++
int minCost(string colors, vector<int>& neededTime) {
int total = 0, i = 0;
int n = (int) colors.size();
while (i < n) {
int j = i, sum = 0, maxT = 0;
while (j < n && colors[j] == colors[i]) {
sum += neededTime[j];
maxT = max(maxT, neededTime[j]);
j++;
}
total += sum - maxT;
i = j;
}
return total;
}JavaScript
var minCost = function(colors, neededTime) {
let total = 0;
let i = 0;
while (i < colors.length) {
let j = i, sum = 0, maxT = 0;
while (j < colors.length && colors[j] === colors[i]) {
sum += neededTime[j];
if (neededTime[j] > maxT) maxT = neededTime[j];
j++;
}
total += sum - maxT;
i = j;
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.