Abstract / Summary

Given a binary string, change any two adjacent differing characters to the same and repeat until no more changes can be made, then find the largest possible resulting string.

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 48% (30k+ submissions).

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 transforms a binary string into its lexicographically largest possible form under a specific set of operations. The algorithm works by consolidating all 1s to the left side of the string while ensuring that exactly one 0 remains, positioned as far right as the transformation rules allow. The core idea is to count leading 1s, total zeros, and then rebuild the string in a single pass without auxiliary data structures.

Initial Scan for Leading Ones

The first loop advances a pointer until it encounters the first 0. This determines how many 1s are already positioned at the leftmost part of the input.

left = 0
while left < len(binary) and binary[left] == "1":
    left += 1

At the end of this segment, left holds the count of consecutive 1s from the start of the string.

Counting All Zeros

A built-in string method tallies the total number of 0 characters in the entire input. This count drives the placement of the single remaining zero in the final result.

zeros = binary.count("0")

If the count is zero, the original string already satisfies the target condition and is returned unchanged.

if zeros == 0:
    return binary

Computing the Final Layout

When zeros are present, the algorithm calculates the number of 1s that will occupy the left segment of the output. The expression left += zeros - 1 adds all but one of the zeros to the left side, effectively converting them into 1s according to the allowed operations.

left += zeros - 1

The remaining characters on the right side are derived by subtracting the left segment and the single zero from the total length.

right = len(binary) - left - 1

Finally, the result string is assembled by concatenating three parts: the left block of 1s, a solitary 0, and the right block of 1s.

return "1" * left + "0" + "1" * right

Edge Cases Handled

The code gracefully manages inputs that consist entirely of 1s. In that scenario zeros equals zero, triggering the early return of the original string. An input composed solely of 0s also works: the initial loop leaves left at zero, zeros equals the string length, and the reconstruction yields a string with a single 0 followed by the appropriate number of 1s, matching the transformation rules. An empty string is implicitly covered because the loop condition fails immediately, zeros is zero, and the function returns the empty input unchanged.

Performance Optimizations

The solution avoids multiple traversals by using a single while loop to locate the first zero and a constant-time count operation that scans the string once more. Both steps are linear in the length of the input, and the subsequent arithmetic calculations are O(1). String construction leverages Python’s multiplication of single-character strings, which is highly optimized in the interpreter, resulting in a fast assembly of the final output without the overhead of list conversions or repeated concatenations. This minimal-footprint approach ensures the algorithm runs efficiently even for very long binary strings.

Imagine holding a long chain of little plastic blocks, where some are green ones and some are empty holes. You want to make the chain look as neat as possible by moving the green blocks to the front.

First, look for the first hole in the chain. Everything before that hole is already a green block, so those stay exactly where they are. Next, count every hole you see hiding in the rest of the chain. Because of the special rules used to play with these blocks, all those holes can be squished together into one single hole.

To build the final chain, put all the green blocks at the very beginning. Then place that one single hole exactly where it needs to go to keep the rest of the chain filled with green blocks until the end. It is like tidying up a messy playroom by putting all the toys in a perfect row and tucking the one messy spot right in the middle of them.

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++	Python		Java				TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java	C#	Go	Rust	TS
	Progiez	C++	Python		Java
github	black-shadows	C++
	charles-wangkai				Java
	fsq	C++
	JoshCrozier			JS
	lkwq007		Python
	suxrobGM					C#
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
wisdompeak	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