Abstract / Summary

You must change the color of some parts of a rope so that no two adjacent parts share the same color using the least time possible.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 65% (600k+ submissions).

Typical patterns to solve this problem:

• Array
• Dynamic Programming
• Greedy
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation computes the minimum total time required to eliminate balloons so that no two adjacent balloons share the same colour. It does this by iterating through the colour string once, maintaining the cost of removals and the highest removal time within each contiguous colour segment. The algorithm accumulates the total removal time, then subtracts the largest time in each segment, effectively keeping the most expensive balloon and discarding the rest.

Initialization

result = 0
prev = ""
high = 0

Three variables are prepared before the scan begins. result holds the cumulative cost of all removals, prev tracks the colour of the previous balloon, and high records the maximum removal time encountered in the current colour block. Starting prev as an empty string guarantees that the first balloon always begins a new block.

Main Loop

for c, t in zip(colors, neededTime):
    result += t  # assume removal of current balloon

    if c == prev:
        high = max(high, t)
    else:
        result -= high  # keep the most expensive balloon of the previous block
        high = t
        prev = c

The loop processes each balloon in lock-step with its removal time. The line result += t initially adds the cost of removing the current balloon, treating every balloon as if it will be discarded. The subsequent conditional distinguishes two situations:

When the current colour matches the previous one (c == prev), the algorithm updates high to the larger of the existing maximum and the current time t. This ensures that high always reflects the most costly balloon in the ongoing colour segment.

When the colour changes (else branch), the algorithm realizes that the previous segment has ended. It subtracts high from result, thereby “keeping” the balloon with the greatest removal time from that segment and discarding the rest. Afterwards it resets high to the current balloon’s time and updates prev to the new colour, establishing the start of a fresh segment.

Final Adjustment

return result - high

After the loop finishes, high still contains the maximum removal time of the last colour segment. The final subtraction removes this value from the accumulated total, mirroring the subtraction performed at each colour transition. The returned value therefore represents the sum of removal times for all balloons except the most expensive one in each contiguous colour block, which is precisely the minimal cost to achieve the required colour separation.

Edge Cases Handled

The algorithm gracefully handles a single-character input because the loop runs once, result receives the sole removal time, and the final subtraction removes that same time, yielding zero - no removal is needed when only one balloon exists. When all balloons share the same colour, the loop never triggers the else branch, so high ends up as the maximum time among all balloons. The final subtraction then leaves the sum of all other times, correctly discarding every balloon except the most expensive one. For alternating colours, each balloon forms its own segment; the else branch executes on every iteration, causing high to be the time of the just-processed balloon, which is then subtracted immediately. The net effect is a zero total cost, as no removals are required when adjacent colours already differ.

Performance Optimizations

The solution achieves its goal with a single pass over the input strings, avoiding any auxiliary data structures such as stacks or additional arrays. By incrementally adding each removal time and later subtracting the maximum of each segment, it eliminates the need for a separate collection of segment elements. The use of zip to iterate over both colors and neededTime in tandem ensures tight coupling of data, reducing indexing overhead. Maintaining only three scalar variables (result, prev, high) keeps the memory footprint constant regardless of input size. These choices collectively deliver an efficient execution path that scales linearly with the length of the input while using minimal extra space.

Imagine a long string of colorful balloons tied together in a line. Some of them are the same color and are sitting right next to each other, which creates a messy clump that needs cleaning up. To make things look tidy, there must be only one balloon of each color left in every group.

The balloons have different amounts of time needed to take them down. To save the most time, the goal is to remove all the extra balloons but keep the one that takes the longest to take down, because that one is effectively free to keep since you would have spent that time anyway.

The computer looks at each balloon one by one. It starts by pretending to take every single balloon down to clear the space. As it moves along, it checks if the current balloon matches the color of the one before it. If they match, the computer remembers which one takes the most time to remove. If the colors are different, the computer realizes it has finished a group. It then gives back the time that was spent on the balloon that took the longest to remove, because that one was allowed to stay. This process continues for all the balloons until the very end, where the computer makes one last check to ensure the final group is handled correctly. By the time the computer reaches the end of the line, the total amount of time spent removing the extra balloons has been tallied up.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java	Python					TS
	WalkCCC	C++	Java	Python
	leetcode.ca	C++	Java	Python			Go	Rust	TS
	Progiez	C++	Java	Python
github	charles-wangkai		Java
	everthis				JS
	fsq	C++
	JoshCrozier				JS
	keineahnung2345	C++
	lkwq007			Python
	suxrobGM					C#
	trung-hn			Python
	varunu28		Java
	vthwang		Java
	wisdompeak	C++
	withaarzoo	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
suxrobGM	C#
trung-hn	Python
varunu28	Java
vthwang	Java
wisdompeak	C++
withaarzoo	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality