Time Needed to Rearrange a Binary String - Solution & Explanation

Problem Overview: You are given a binary string. Every second, all occurrences of "01" are replaced with "10" simultaneously. The task is to compute how many seconds are required until the string stops changing.

Approach 1: Simulate Step-by-Step Transformations (O(n²) time, O(1) space)

The most direct method mimics the process exactly as described. Scan the string from left to right and swap every "01" pair into "10" during a single pass. After completing one pass, increment the time counter and repeat until no more swaps occur. Each iteration pushes 1s to the right by at most one position, similar to bubble sort behavior.

This approach uses simple string or array manipulation and falls under simulation. In the worst case (for example "000...111" patterns gradually moving), the process may require up to n passes with an O(n) scan each time, resulting in O(n²) time. Space usage stays O(1) since swaps occur in place.

Approach 2: Analytical Total Number of 01 Pairs (O(n) time, O(1) space)

The simulation hides a useful observation: each 1 must move past all preceding 0s. Instead of performing swaps, track how many zeros appear before each 1. When scanning the string, maintain a counter zeros. Every time a 0 appears, increment it. When encountering a 1 with zeros > 0, that 1 must cross those zeros.

The key detail is that movements cannot happen simultaneously for the same character if previous swaps delay it. Maintain a variable time. For each such 1, update time = max(time + 1, zeros). This models both waiting for earlier swaps and the distance the 1 must travel. The entire string is processed in one pass, making the algorithm O(n) time with O(1) extra space.

This method relies on recognizing the implicit ordering constraints created by repeated swaps, a pattern common in string processing problems and occasionally framed with dynamic programming-style state transitions.

Recommended for interviews: Interviewers usually expect the analytical approach. Writing the simulation first shows you understand the process, but the O(n) counting method demonstrates stronger algorithmic insight by eliminating unnecessary passes.