Minimum Time to Make Rope Colorful
Problem
colors[i] is the i-th balloon's color, neededTime[i] its removal cost. Return the minimum total time to remove balloons so no two consecutive have the same color.
colors="abaac", neededTime=[1,2,3,4,5]3def min_cost(colors, neededTime):
ans = i = 0; n = len(colors)
while i < n:
j = i; total = mx = 0
while j < n and colors[j] == colors[i]:
total += neededTime[j]; mx = max(mx, neededTime[j]); j += 1
ans += total - mx; i = j
return ansfunction minCost(colors, neededTime) {
let ans = 0, i = 0, n = colors.length;
while (i < n) {
let j = i, total = 0, mx = 0;
while (j < n && colors[j] === colors[i]) { total += neededTime[j]; if (neededTime[j] > mx) mx = neededTime[j]; j++; }
ans += total - mx; i = j;
}
return ans;
}class Solution {
public int minCost(String colors, int[] neededTime) {
int ans = 0, i = 0, n = colors.length();
while (i < n) {
int j = i, total = 0, mx = 0;
while (j < n && colors.charAt(j) == colors.charAt(i)) { total += neededTime[j]; mx = Math.max(mx, neededTime[j]); j++; }
ans += total - mx; i = j;
}
return ans;
}
}int minCost(string colors, vector& neededTime) {
int ans = 0, i = 0, n = colors.size();
while (i < n) {
int j = i, total = 0, mx = 0;
while (j < n && colors[j] == colors[i]) { total += neededTime[j]; mx = max(mx, neededTime[j]); j++; }
ans += total - mx; i = j;
}
return ans;
} Explanation
Wherever several balloons of the same color sit in a row, we must remove enough of them so only one survives. To pay the least, we keep the most expensive one in that run and delete the rest.
The code scans the string and groups each run of equal colors. The inner while loop walks from i as long as the color stays the same, summing the costs into total and tracking the largest single cost mx.
For that run, the cost to clean it is total - mx: we pay for everything except the priciest balloon, which we keep. We add that to ans and jump i to j, the start of the next run.
Runs of length one cost nothing (total == mx), so they are naturally skipped. Summing across all runs gives the minimum total time.
Example: colors = "abaac", neededTime = [1,2,3,4,5]. The only repeated run is "aa" at indices 2 and 3 with costs 3 and 4; we keep the 4 and remove the 3, so the answer is 3.