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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


    
    
    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

1
2
3
4
5
6
7
8
9


    
    
    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?

Solution

Method 1 – Greedy Simulation (O(n))

Intuition

Track the number of 1’s to the left of each 0, and for each 0, compute how many steps it takes to move past all 1’s to its left. The answer is the maximum such value.

Approach

Iterate through the string, for each 0, count how many 1’s have been seen so far. The time for this 0 is the maximum of (previous time + 1) and the number of 1’s seen so far. The answer is the maximum time for any 0.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def secondsToRemoveOccurrences(self, s: str) -> int:
        ans = ones = 0
        for c in s:
            if c == '1':
                ones += 1
            else:
                if ones > 0:
                    ans = max(ans + 1, ones)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public int secondsToRemoveOccurrences(String s) {
        int ans = 0, ones = 0;
        for (char c : s.toCharArray()) {
            if (c == '1') ones++;
            else if (ones > 0) ans = Math.max(ans + 1, ones);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)