# Time Needed to Rearrange a Binary String
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/time-needed-to-rearrange-a-binary-string)
Canonical: https://scaleengineer.com/dsa/problems/time-needed-to-rearrange-a-binary-string
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** String
**Companies:** [PayPal](https://scaleengineer.com/companies/paypal), [ServiceNow](https://scaleengineer.com/companies/servicenow)
---
## Problem
You are given a binary string `s`. In one second, **all** occurrences of `"01"` are **simultaneously** replaced with `"10"`. This process **repeats** until no occurrences of `"01"` exist.

Return _the number of seconds needed to complete this process._

**Example 1:**

**Input:** s = "0110101"
**Output:** 4
**Explanation:** 
After one second, s becomes "1011010".
After another second, s becomes "1101100".
After the third second, s becomes "1110100".
After the fourth second, s becomes "1111000".
No occurrence of "01" exists any longer, and the process needed 4 seconds to complete,
so we return 4.

**Example 2:**

**Input:** s = "11100"
**Output:** 0
**Explanation:**
No occurrence of "01" exists in s, and the processes needed 0 seconds to complete,
so we return 0.

**Constraints:**

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

**Follow up:**

Can you solve this problem in O(n) time complexity?

# Approaches
## Brute Force Simulation
The most intuitive way to solve this problem is to directly simulate the process described. We can model the passage of time with a loop, where each iteration represents one second. In each second, we scan the string and identify all occurrences of `"01"`. We then replace them with `"10"` to produce the string's state for the next second. This process is repeated until no `"01"` substrings exist in the string. The total number of iterations will be the answer.
**Time:** O(N * T), where N is the length of the string and T is the total number of seconds required. In the worst-case scenario, like the string `"011...1"`, a single '0' has to move N-1 positions, taking one second per position. Thus, T can be up to O(N), making the total time complexity O(N^2). · **Space:** O(N), where N is the length of the string. This is because in each iteration of the simulation, we create a new `StringBuilder` or string of length N to store the state of the string for the next second.
**Pros:** The logic is straightforward and easy to implement as it directly follows the problem statement.; It is guaranteed to be correct.
**Cons:** The time complexity of O(N^2) can be too slow if the input string length `N` is large.; It creates a new string or `StringBuilder` in every iteration, which can be memory-intensive for very long strings, although within the given constraints it's acceptable.
### Explanation
To implement this, we can use a `while` loop that continues as long as swaps are being made. Inside the loop, we count a second and then construct the next state of the string. A crucial detail is that all swaps happen simultaneously. This means we must base our swaps on the string's state at the beginning of the second. A simple way to achieve this is to build a new string (or `StringBuilder`) for the next state, rather than modifying the string in-place. We iterate through the current string, and whenever we see a `"01"`, we append `"10"` to our new string. Otherwise, we append the character we are currently at. After the pass is complete, we update the current string to the new one we just built. If a pass completes with no swaps made, we have reached the final state and can stop.

```java
class Solution {
    public int secondsToRemoveOccurrences(String s) {
        int seconds = 0;
        StringBuilder currentS = new StringBuilder(s);
        
        while (true) {
            boolean foundSwap = false;
            int i = 0;
            while (i < currentS.length() - 1) {
                if (currentS.charAt(i) == '0' && currentS.charAt(i + 1) == '1') {
                    foundSwap = true;
                    break;
                }
                i++;
            }

            if (!foundSwap) {
                break;
            }

            seconds++;
            StringBuilder nextS = new StringBuilder();
            i = 0;
            while (i < currentS.length()) {
                if (i + 1 < currentS.length() && currentS.charAt(i) == '0' && currentS.charAt(i + 1) == '1') {
                    nextS.append("10");
                    i += 2;
                } else {
                    nextS.append(currentS.charAt(i));
                    i++;
                }
            }
            currentS = nextS;
        }
        
        return seconds;
    }
}
```
### Algorithm
*   Initialize a counter `seconds` to 0.
*   Start a loop that continues as long as the string contains the substring `"01"`.
*   Inside the loop, increment `seconds`.
*   To handle the simultaneous replacement of all `"01"` occurrences, we must build a new version of the string in each iteration. A `StringBuilder` is suitable for this.
*   Iterate through the current string's characters. If we find a `"01"` pattern starting at index `i`, we append `"10"` to our `StringBuilder` and advance our loop counter by 2. 
*   Otherwise, we append the current character and advance by 1.
*   After iterating through the entire string, we update our main string to this new version.
*   The loop terminates when a full pass over the string finds no `"01"` substrings. The value of `seconds` is the result.

## Linear Time One-Pass Approach
Instead of a full simulation, we can find the answer in a single pass. The key idea is to analyze the constraints on the time required for the swaps. The total time is determined by the '0' that takes the longest to reach its final sorted position. This time is affected by the number of '1's it needs to pass and the number of other '0's that might be blocking its path. We can formulate a dynamic programming-like relation by iterating through the string and keeping track of the number of '0's seen and the time elapsed so far.
**Time:** O(N), where N is the length of the string. This is because we perform a single pass through the string. · **Space:** O(1), as we only use a few variables (`zeros`, `seconds`) to keep track of the state, regardless of the input string size.
**Pros:** Extremely efficient with a linear time complexity.; Uses constant extra space, making it very memory-efficient.
**Cons:** The logic is more abstract and less intuitive than the direct simulation, requiring a deeper understanding of the underlying process.
### Explanation
We can iterate through the string from left to right, maintaining a count of zeros (`zeros`) seen so far and the calculated time (`seconds`). When we encounter a '0', we just increment `zeros`. When we encounter a '1', if there are any zeros to its left (`zeros > 0`), we know swaps must occur. The time required for these swaps is determined by the more restrictive of two conditions. First, any '0' that was already part of a `seconds`-long swap sequence will need one more second to get past this new '1', so the time must be at least `seconds + 1`. Second, a group of `zeros` '0's takes `zeros` seconds to move past a single '1'. Therefore, the updated time must be the maximum of these two values. This single pass correctly accumulates the maximum time required by any '0' to find its final position.

```java
class Solution {
    public int secondsToRemoveOccurrences(String s) {
        int zeros = 0;
        int seconds = 0;
        for (char c : s.toCharArray()) {
            if (c == '0') {
                zeros++;
            } else if (zeros > 0) {
                // This '1' must be swapped with the '0's on its left.
                // The time is constrained by two factors:
                // 1. A '0' that took `seconds` to get to the position just before this '1'
                //    needs one more second to pass it. Time >= seconds + 1.
                // 2. A block of `zeros` '0's needs `zeros` seconds to pass this '1'.
                //    Time >= zeros.
                // The new time must satisfy both, so we take the maximum.
                seconds = Math.max(seconds + 1, zeros);
            }
        }
        return seconds;
    }
}
```
### Algorithm
*   Initialize two integer variables: `zeros = 0` to count the number of '0's encountered so far, and `seconds = 0` to store the result.
*   Iterate through the input string `s` from left to right, character by character.
*   If the current character is `'0'`, increment the `zeros` counter.
*   If the current character is `'1'`:
    *   Check if `zeros > 0`. If not, this '1' is already in a sorted position relative to the characters seen so far, so we do nothing.
    *   If `zeros > 0`, it means this '1' must move left past all the `zeros` '0's we've seen. This process takes time. The total time (`seconds`) is constrained by two factors:
        1.  A '0' that was already moving for `seconds` seconds needs one additional second to pass the current '1'. This implies the new time must be at least `seconds + 1`.
        2.  A contiguous block of `zeros` '0's needs `zeros` seconds to fully move past a single '1' (e.g., `"001"` -> `"010"` -> `"100"` takes 2 seconds). This implies the time must be at least `zeros`.
    *   To satisfy both constraints, we update `seconds = Math.max(seconds + 1, zeros)`.
*   After iterating through the entire string, the `seconds` variable will hold the total time needed.

# Solutions
### Java

```java
class Solution {
public
  int secondsToRemoveOccurrences(String s) {
    char[] cs = s.toCharArray();
    boolean find = true;
    int ans = 0;
    while (find) {
      find = false;
      for (int i = 0; i < cs.length - 1; ++i) {
        if (cs[i] == '0' && cs[i + 1] == '1') {
          char t = cs[i];
          cs[i] = cs[i + 1];
          cs[i + 1] = t;
          ++i;
          find = true;
        }
      }
      if (find) {
        ++ans;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int secondsToRemoveOccurrences(string s) {
    bool find = true;
    int ans = 0;
    while (find) {
      find = false;
      for (int i = 0; i < s.size() - 1; ++i) {
        if (s[i] == '0' && s[i + 1] == '1') {
          swap(s[i], s[i + 1]);
          ++i;
          find = true;
        }
      }
      if (find) {
        ++ans;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def secondsToRemoveOccurrences(self, s: str) -> int: ans = 0 while s . count('01'): s = s . replace('01', '10') ans += 1 return ans

```