Time Needed to Rearrange a Binary String

Medium
1236.

Time Needed to Rearrange a Binary String

Time Needed to Rearrange a Binary String is a medium coding problem on strings, dynamic programming and simulation, asked in Amazon and Google interviews.

You are given a binary string s. Every second, all occurrences of the substring "01" are replaced by "10" at the same time. The process repeats until s contains no "01" at all.

Return the number of seconds the process takes.

Example 1

Input
s = "0011"
Output
3
Explanation
`0011` → `0101` → `1010` → `1100`.

Example 2

Input
s = "1001"
Output
2
Explanation
`1001` → `1010` → `1100`.

Example 3

Input
s = "1100"
Output
0
Explanation
There is no `"01"` to begin with.

Constraints

  • 1 <= s.length <= 1000
  • s[i] is either '0' or '1'

Follow-up: Can you solve it in O(n) time?

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var secondsToRemoveOccurrences = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Time Needed to Rearrange a Binary String — Solution

Time Needed to Rearrange a Binary String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Time Needed to Rearrange a Binary String is a medium coding problem on strings, dynamic programming and simulation, asked in Amazon and Google interviews.

Problem statement

You are given a binary string s. Every second, all occurrences of the substring "01" are replaced by "10" at the same time. The process repeats until s contains no "01" at all.

Return the number of seconds the process takes.

Example 1

Input: s = "0011"
Output: 3
Explanation: `0011` → `0101` → `1010` → `1100`.

Example 2

Input: s = "1001"
Output: 2
Explanation: `1001` → `1010` → `1100`.

Example 3

Input: s = "1100"
Output: 0
Explanation: There is no `"01"` to begin with.

Constraints

  • 1 <= s.length <= 1000
  • s[i] is either '0' or '1'

Follow-up: Can you solve it in O(n) time?

Hints for Time Needed to Rearrange a Binary String

  1. Hint 1

    In the end every 1 sits to the left of every 0. Each second, a 1 with a 0 directly to its left moves one step left.

  2. Hint 2

    A 1 needs at least as many seconds as there are 0s before it — it must pass each of them.

  3. Hint 3

    It may also be blocked by the 1 in front of it, finishing at least one second after that one. Sweep left to right: ans = max(ans + 1, zeros) at each 1 that has a 0 before it.

How to solve Time Needed to Rearrange a Binary String

Track when each 1 finishes moving. A 1 with z zeros before it needs at least z seconds, and it finishes at least one second after the previous moving 1, which can block it.

Approach

  1. Sweep s from left to right, counting zeros, the 0s seen so far, and keeping ans, the finishing time of the last 1 that had to move.
  2. On a 0, increase zeros.
  3. On a 1 with zeros > 0, set ans = max(ans + 1, zeros). A 1 with no 0 before it never moves and changes nothing.
  4. Return ans.

Why it works

Each second a moving 1 advances one place unless the 1 directly ahead of it is still sitting in its way. If it is never blocked it finishes after exactly zeros seconds. If it catches up with the previous moving 1, it from then on trails it by one second, finishing at previous + 1. Its true finishing time is the larger of these two bounds, and the last 1 to finish determines the whole process.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Leading 1s do not move; do not let them bump ans.
  • Simulating directly costs O(n²) — acceptable for n = 1000, but the sweep is linear.
  • Replacements happen simultaneously, so a 1 moves at most one place per second.

Reference solution

Python

def secondsToRemoveOccurrences(s: str) -> int:
    zeros = 0
    ans = 0
    for ch in s:
        if ch == "0":
            zeros += 1
        elif zeros > 0:
            ans = max(ans + 1, zeros)
    return ans

Java

public static int secondsToRemoveOccurrences(String s) {
    int zeros = 0, ans = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '0') zeros++;
        else if (zeros > 0) ans = Math.max(ans + 1, zeros);
    }
    return ans;
}

C++

int secondsToRemoveOccurrences(string s) {
    int zeros = 0, ans = 0;
    for (char ch : s) {
        if (ch == '0') zeros++;
        else if (zeros > 0) ans = max(ans + 1, zeros);
    }
    return ans;
}

JavaScript

var secondsToRemoveOccurrences = function(s) {
    var zeros = 0, ans = 0;
    for (var i = 0; i < s.length; i++) {
        if (s[i] === "0") zeros++;
        else if (zeros > 0) ans = Math.max(ans + 1, zeros);
    }
    return ans;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Dynamic Programming