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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Time Needed to Rearrange a Binary String

Number: 2464

Difficulty: Medium

Paid? No

Companies: ServiceNow, PayPal, Amazon

Problem Description

Given a binary string s, in one second all occurrences of the substring "01" are simultaneously replaced by "10". This process is repeated until no "01" substring exists. The task is to determine the total number of seconds required to complete this process.

Key Insights

  • The process moves all 1s toward the left and 0s to the right.
  • The transformation "01" → "10" happens simultaneously each second, so careful simulation is needed.
  • The process stops when no adjacent pair "01" is found.
  • While a simulation approach with O(n²) worst-case complexity is acceptable given the input size (n <= 1000), an O(n) solution might be deducible by observing how far each 1 needs to travel.

Space and Time Complexity

Time Complexity: O(n * T) where T is the number of seconds (worst-case O(n²) for n=1000 using simulation)
Space Complexity: O(n) for storing the updated string representation

Solution

We can solve this problem by simulating each second. At every time step, we scan the string for any occurrence of "01". Once found, we record these indices and perform the swaps simultaneously to form the new string for the next iteration. We repeat this process until the string no longer contains any "01" pairs.

This simulation mimics the transformation exactly as described, ensuring that we account for simultaneous swapping (i.e. one swap does not affect another in the same second). Key structures used include an array (or list) to hold the mutable string, and loop control to manage scanning and swapping. The primary trick is to skip an index after performing a swap to avoid overlapping swaps within the same second.

Code Solutions

# Python solution for "Time Needed to Rearrange a Binary String"
def secondsToRemoveOccurrences(s: str) -> int:
    seconds = 0
    # Continue simulation until no "01" pattern exists in the string.
    while "01" in s:
        # Convert string to list for easier swapping.
        chars = list(s)
        i = 0
        # Process the entire string for this second.
        while i < len(s) - 1:
            if s[i] == '0' and s[i + 1] == '1':
                # Swap the pair and skip the next index since it's part of this swap.
                chars[i], chars[i + 1] = chars[i + 1], chars[i]
                i += 2  # Move two positions ahead as the swap covers two characters.
            else:
                i += 1
        # Update the string for the next iteration.
        s = "".join(chars)
        seconds += 1
    return seconds

# Example usage:
print(secondsToRemoveOccurrences("0110101"))  # Expected output: 4
← Back to All Questions