LeetCode 2380 - Time Needed to Rearrange a Binary String

Difficulty: 🟡 Medium
Topics: String, Dynamic Programming, Simulation

Solution

Problem Understanding

This problem asks us to repeatedly transform a binary string according to a very specific rule. During each second, every occurrence of the substring "01" is replaced simultaneously with "10".

The important detail is that all replacements happen at the same time. This means we do not process one occurrence at a time from left to right. Instead, every "01" pair in the string swaps simultaneously during a single second.

We continue performing these transformations until the string no longer contains "01". At that point, all '1' characters must already be positioned before all '0' characters, because "01" represents a situation where a '1' can still move leftward relative to a '0'.

The goal is to return the number of seconds required before no more "01" substrings exist.

For example, given:

"0110101"

the process evolves like this:

After 4 seconds, there are no remaining "01" patterns, so the answer is 4.

The constraints are relatively small, with the string length at most 1000. This means even an O(n²) solution would likely pass. However, the follow up explicitly asks whether we can solve it in O(n) time, which strongly suggests there is an observation that avoids repeated simulation.

Several edge cases are important to recognize upfront. A string that already contains no "01" pattern, such as "11100", should immediately return 0. A string made entirely of '0' or entirely of '1' also requires 0 seconds. Alternating patterns like "010101" are tricky because many swaps happen simultaneously, which can mislead naive sequential simulations. Long chains of zeros followed by ones also require careful reasoning because a single '1' may need multiple seconds to move past multiple zeros.

Approaches

Brute Force Simulation

The most direct approach is to literally simulate the process exactly as described.

At each second, we scan the string and replace every "01" with "10" simultaneously. Since simultaneous replacement matters, we cannot simply swap characters in place during iteration because earlier swaps would incorrectly affect later ones. Instead, we would construct a new string for each second.

We repeat this process until the string no longer contains "01" and count how many iterations were needed.

This approach is correct because it faithfully reproduces the exact transformation rules given in the problem statement. Every second corresponds to one complete pass of simultaneous replacements.

However, it is inefficient. In the worst case, we may need O(n) seconds, and each second requires scanning the whole string of length n. Therefore, the total time complexity becomes O(n²).

Optimal Observation, Counting Delays

The key insight is that we do not actually need to simulate every second.

Each '1' wants to move left across zeros. Every time a '1' encounters a zero before it, it eventually swaps past it. If there are k zeros before a '1', then that '1' needs at least k seconds to fully move left.

However, there is an additional complication. Multiple '1' characters can block each other. Even if a '1' has enough zeros to cross, it may have to wait for earlier '1' characters to finish moving first.

We process the string from left to right and track:

zero_count, the number of zeros encountered so far
seconds, the maximum time needed so far

When we see a '0', we increment zero_count.

When we see a '1', if there are zeros before it, this '1' must move. The time needed becomes:

max(seconds + 1, zero_count)

This formula captures two constraints:

zero_count, because the '1' must cross that many zeros
seconds + 1, because consecutive '1' characters may need to wait one extra second behind previous ones

This lets us compute the answer in a single pass.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Simulates every second by rebuilding the string
Optimal	O(n)	O(1)	Tracks zero count and movement delays in one pass

Algorithm Walkthrough

Initialize two variables:

zero_count = 0, representing how many zeros have appeared so far.
seconds = 0, representing the maximum time needed for rearrangement so far.

Iterate through the string character by character from left to right.
If the current character is '0', increment zero_count. This matters because every future '1' must eventually move past these zeros.
If the current character is '1' and zero_count > 0, this '1' must move left past earlier zeros.
Compute the required time for this '1':

seconds = max(seconds + 1, zero_count)

This ensures two conditions:

The '1' crosses all preceding zeros, requiring at least zero_count seconds.
If previous '1' characters are already moving, this '1' cannot overtake them, so it may need to wait an extra second.

Continue until the entire string has been processed.
Return seconds, which represents the total number of seconds needed.

Why it works

The invariant is that seconds always represents the minimum time needed to fully arrange all '1' characters processed so far. For each '1', the algorithm considers both its own movement requirement, determined by how many zeros precede it, and any waiting time caused by earlier '1' characters. Since every '1' is processed exactly once and its movement dependencies are accounted for, the final seconds value is exactly the number of simultaneous swap rounds required.

Python Solution

class Solution:
    def secondsToRemoveOccurrences(self, s: str) -> int:
        zero_count = 0
        seconds = 0

        for char in s:
            if char == '0':
                zero_count += 1
            elif zero_count > 0:
                seconds = max(seconds + 1, zero_count)

        return seconds

The implementation closely follows the optimal algorithm.

We begin by initializing zero_count and seconds. As we scan the string, every '0' increases zero_count, since it creates an obstacle for future '1' characters.

When we encounter a '1', we check whether any zeros came before it. If zero_count > 0, this '1' must eventually move. We update seconds using:

max(seconds + 1, zero_count)

The zero_count term ensures the '1' has enough time to pass all preceding zeros. The seconds + 1 term ensures it respects the movement ordering of previous '1' characters and does not unrealistically overtake them.

Finally, after processing the whole string, we return seconds.

Go Solution

func secondsToRemoveOccurrences(s string) int {
    zeroCount := 0
    seconds := 0

    for _, char := range s {
        if char == '0' {
            zeroCount++
        } else if zeroCount > 0 {
            if seconds+1 > zeroCount {
                seconds = seconds + 1
            } else {
                seconds = zeroCount
            }
        }
    }

    return seconds
}

The Go implementation follows the same logic as the Python solution.

Since Go does not have a built in max function for integers, we explicitly compare seconds + 1 and zeroCount using an if statement. Strings in Go are iterated as runes, but since the input contains only '0' and '1', this works efficiently and safely.

There are no concerns about integer overflow because the maximum string length is only 1000, meaning the answer remains very small.

Worked Examples

Example 1

Input:

s = "0110101"

We track zero_count and seconds during iteration.

Index	Character	zero_count	seconds	Explanation
0	0	1	0	Found a zero
1	1	1	1	`max(0+1,1)=1`
2	1	1	2	Must wait behind previous `1`
3	0	2	2	Another zero added
4	1	2	3	`max(2+1,2)=3`
5	0	3	3	Another zero
6	1	3	4	`max(3+1,3)=4`

Final answer:

This matches the simulation:

Example 2

Input:

s = "11100"

Index	Character	zero_count	Explanation
0	1	0	No preceding zero
1	1	0	No movement needed
2	1	0	No movement needed
3	0	1	Zero encountered
4	0	2	Zero encountered

Final answer:

No "01" pattern exists initially, so no swaps occur.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We scan the string exactly once
Space	O(1)	Only a few integer variables are used

The algorithm is linear because every character is processed exactly one time. No nested loops or repeated simulations are needed. Space usage remains constant since we only maintain two integer counters regardless of input size.

Test Cases

solution = Solution()

assert solution.secondsToRemoveOccurrences("0110101") == 4  # Provided example
assert solution.secondsToRemoveOccurrences("11100") == 0  # Already stable

assert solution.secondsToRemoveOccurrences("0") == 0  # Single zero
assert solution.secondsToRemoveOccurrences("1") == 0  # Single one

assert solution.secondsToRemoveOccurrences("0000") == 0  # All zeros
assert solution.secondsToRemoveOccurrences("1111") == 0  # All ones

assert solution.secondsToRemoveOccurrences("01") == 1  # Single swap
assert solution.secondsToRemoveOccurrences("10") == 0  # Already ordered

assert solution.secondsToRemoveOccurrences("0101") == 2  # Alternating pattern
assert solution.secondsToRemoveOccurrences("00111") == 4  # Ones crossing multiple zeros

assert solution.secondsToRemoveOccurrences("101010") == 2  # Mixed arrangement
assert solution.secondsToRemoveOccurrences("000111") == 5  # Large movement chain

Test	Why
`"0110101"`	Validates provided example
`"11100"`	Ensures already stable strings return `0`
`"0"`	Smallest valid input with zero
`"1"`	Smallest valid input with one
`"0000"`	All zeros edge case
`"1111"`	All ones edge case
`"01"`	Simplest possible swap
`"10"`	Already sorted order
`"0101"`	Simultaneous swaps in alternating pattern
`"00111"`	Multiple ones crossing zeros
`"101010"`	Mixed arrangement with staggered movement
`"000111"`	Worst style movement pattern

Edge Cases

Already Stable String

A string like "11100" already has all '1' characters before '0' characters. Since there are no "01" substrings, the answer should be 0. A buggy implementation might unnecessarily simulate swaps or miscount movements. Our algorithm handles this naturally because no '1' ever encounters a preceding zero.

Single Character Input

Inputs like "0" or "1" are the smallest valid strings. Since no adjacent pair exists, no swap is possible. The implementation correctly returns 0 because the loop either increments zero_count once or skips movement logic entirely.

Multiple Consecutive Ones Waiting

A case like "00111" is subtle because later '1' characters may need to wait behind earlier ones. Although each '1' sees the same number of preceding zeros, they cannot all move simultaneously without interference. The max(seconds + 1, zero_count) formula correctly models this waiting behavior, preventing undercounting.

Alternating Patterns

Strings such as "010101" contain many simultaneous swaps. A naive sequential swap implementation could accidentally process swaps one at a time and produce incorrect intermediate states. Since the optimal solution reasons mathematically about movement instead of simulating swaps directly, simultaneous behavior is handled correctly.