Ones Slip to the Front

Medium

You get a string bits of 0 and 1 characters. Every second, all occurrences of "01" are replaced with "10" at the same time: every 1 that has a 0 right before it swaps places with that 0. This repeats while the string still contains "01". Return how many seconds the process takes. Direct simulation runs in O(n²). Can you do it in O(n)?

Example 1

bits="1001" → 2

"1001" → "1010" → "1100": two seconds.

Example 2

bits="0011" → 3

"0011" → "0101" → "1010" → "1100". The second 1 has to wait for the first one to clear the way, so it takes three seconds, not two.

Example 3

bits="110" → 0

There is no "01" from the very start.

Constraints

1 ≤ len(bits) ≤ 1000
bits contains only 0 and 1

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

String Dynamic Programming Simulation

Similar problems

Longest Mirror Fragment Medium All Balanced Bracket Strings Medium Multiplying Digit Strings Medium Fewest Letter Edits Medium Ways to Read a Digit Code Medium

Input

bits="1001"

Expected

Run checks the first 3 tests in your browser. Submit checks all 130 tests on the server, hidden ones included.