We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Time Needed to Rearrange a Binary String

Difficulty: Medium

Problem Description

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.

Key Insights

  • The process involves simultaneous replacements of "01" with "10".
  • The number of seconds needed is determined by how many iterations it takes for all "01" patterns to be eliminated.
  • Each iteration can be thought of as a wave moving through the string, where "01" patterns are flipped to "10".
  • The maximum distance between the leftmost '0' and the rightmost '1' in the string determines how many seconds are needed.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve the problem, we can use a linear scan approach to find the positions of the leftmost '0' and the rightmost '1'. The number of seconds needed to eliminate all "01" patterns will be equal to the maximum distance between these two indices, as each second allows the "01" pairs to be flipped. The algorithm will iterate through the string once, making it O(n) in time complexity.

Code Solutions

def seconds_to_rearrange(s: str) -> int:
    leftmost_zero = -1
    rightmost_one = -1
    
    # Find the leftmost '0' and the rightmost '1'
    for i in range(len(s)):
        if s[i] == '0' and leftmost_zero == -1:
            leftmost_zero = i
        if s[i] == '1':
            rightmost_one = i
            
    # If there's no '0' or no '1', return 0 seconds
    if leftmost_zero == -1 or rightmost_one == -1:
        return 0
        
    # The number of seconds is the distance between these two positions
    return max(0, rightmost_one - leftmost_zero)

# Example usage
print(seconds_to_rearrange("0110101"))  # Output: 4
print(seconds_to_rearrange("11100"))    # Output: 0
← Back to All Questions