Abstract / Summary

You must count the minimum steps to move all zeros to one end by swapping adjacent characters.

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 53% (80k+ submissions).

Typical patterns to solve this problem:

• Dynamic Programming
• Simulation
• 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 defines a class Solution with a single method secondsToRemoveOccurrences. The method receives a binary string s and returns the number of seconds required to eliminate all occurrences of the substring "01" by repeatedly swapping each "01" to "10" in a single second. The algorithm proceeds by iteratively applying a global replacement until the string stabilizes, counting each iteration as one second.

Core Loop

The heart of the algorithm is an infinite while loop that repeatedly transforms the string and checks for convergence.

seconds = 0
while True:
    t = s.replace("01", "10")
    if s == t:  # no more changes ?
        return seconds
    s = t
    seconds += 1

Inside the loop, the current state s is transformed into a new string t where every non-overlapping occurrence of "01" is replaced by "10". The loop terminates when the transformation produces no change, indicating that the string no longer contains the pattern "01".

Replacement Operation

The line t = s.replace("01", "10") leverages Python’s built-in str.replace method. This method scans the original string from left to right, identifies each non-overlapping occurrence of the target substring "01", and substitutes it with "10". Because the replacement string has the same length as the target, the overall length of the string remains constant throughout the process. The operation is performed in a single pass, which is more efficient than manually iterating over characters and performing conditional swaps.

Termination Condition

The condition if s == t: serves as a precise check for the absence of further "01" patterns. When the replacement yields an identical string, it guarantees that no "01" substrings exist, because any such pattern would have been transformed. At that point, the method returns the accumulated seconds counter, representing the total number of transformation steps required.

Edge Cases

The algorithm gracefully handles several edge scenarios without additional code:

• An empty string results in an immediate termination because the replacement produces the same empty string, and the method returns 0.
• Strings composed entirely of '0' characters contain no "01" pattern, so the first replacement leaves the string unchanged and the method returns 0.
• Strings composed entirely of '1' characters behave similarly, also returning 0.
• A string that already lacks the "01" pattern, such as "111000" or "10", triggers the termination condition on the first iteration, yielding a result of 0.
• For a string consisting of a single character, either '0' or '1', the replacement does nothing, and the method returns 0.

These cases are implicitly covered because the replace operation does not modify strings that lack the target substring, and the equality check detects the lack of change instantly.

Performance Optimizations

The implementation benefits from two notable optimizations inherent to the Python runtime:

• The use of the native str.replace method avoids explicit Python-level loops, allowing the operation to be executed in highly optimized C code. This reduces interpreter overhead and improves throughput for each iteration.
• By performing a whole-string replacement in one call, the algorithm eliminates the need for auxiliary data structures such as character arrays or temporary buffers. The memory footprint stays minimal, as each iteration creates only a single new string object t, which replaces the reference to the previous string s.

Together, these choices ensure that each second of simulated time is processed with maximal efficiency given the constraints of the problem.

Imagine a long line of toy trains sitting on a track. Some of the trains are labeled with a zero and some are labeled with a one. When a zero is standing right in front of a one, they get a little silly and decide to swap places so the one is in front.

This code works like a timer for those trains. It watches the whole line and spots every pair of a zero and a one that are standing in the wrong order. Once it finds them, it lets them swap places at the exact same time. The code keeps track of how many times this happens by counting each second that passes.

It keeps looking at the line over and over again to see if any more trains are still misplaced. As long as it can find a zero sitting in front of a one, it keeps swapping them and stays busy counting. When the line is finally finished and no more trains need to move because all the ones are safely in front of the zeros, the counting stops.

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

Time: polynomial
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		Java	C++	Python		TS
	WalkCCC		Java	C++	Python
	leetcode.ca		Java	C++	Python	Go
	Progiez		Java	C++	Python
github	charles-wangkai		Java
	everthis	JS
	fsq			C++
	JoshCrozier	JS
	lkwq007				Python
	varunu28		Java
	wisdompeak			C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
varunu28	Java
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