Minimum Time to Make Rope Colorful
Core idea: walk the string in runs of identical adjacent colors; for each run you must keep exactly one balloon, so keep the most expensive and pay to remove all the rest.
Problem, rephrased
Imagine a string of holiday lights strung along a wire. Each bulb has a color and a swap cost (how many seconds it takes the electrician to unclip it). The rule for a "tidy" string is simple: no two neighbouring bulbs may share a color. You may unclip as many bulbs as you like; the bill is the sum of the swap costs of everything you removed. Find the cheapest way to make the whole string tidy.
The key realization: a "tidy" string only forbids adjacent equal colors. So a maximal block of identical colors (a run) like bbbb must be thinned down until only one bulb of that color survives in that spot. You're free to choose which one survives — so you keep the priciest and remove the cheaper ones.
You're given:
colors— a string, one character per bulb.neededTime— an integer array of the same length;neededTime[i]is the cost to remove bulbi.
Return the minimum total removal cost.
colors |
neededTime |
Output | Why |
|---|---|---|---|
"abc" |
[1, 2, 3] |
0 |
No two neighbours match — already tidy. |
"aaab" |
[1, 2, 3, 4] |
3 |
Run aaa (costs 1,2,3): keep the 3, remove 1+2 = 3. |
"aabaa" |
[1, 2, 3, 4, 1] |
2 |
Run aa keep 2 remove 1; run aa keep 4 remove 1; total 2. |
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson