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

Maximum Binary String After Change

Number: 1804

Difficulty: Medium

Paid? No

Companies: Huawei

Problem Description

Given a binary string composed only of '0's and '1's, you can perform two operations any number of times:

  1. Replace any occurrence of "00" with "10".
  2. Replace any occurrence of "10" with "01".

The goal is to determine the maximum possible binary string (with respect to the numeric value when viewed as a binary number) that can be obtained after performing these operations.

Key Insights

  • If the string has no "00" or only a single '0', no operation can increase its value.
  • The operations always tend to move '1's to the left and shift '0's to the right.
  • Ultimately, if there is at least one "00", the maximum string can be formed by turning as many '0's as possible into '1's.
  • The final string will have a contiguous block of '1's, then a single '0', followed by all remaining '1's.
  • The position of the first '0' in the original string and the total count of '0's determine the exact formation of the final string.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string (we perform one pass or two passes over the input). Space Complexity: O(n) for constructing the new string, or O(1) extra space if using in-place modifications in some languages.

Solution

We first check if the binary string has fewer than two '0's. If yes, no transformation can improve its value, and we return the input string directly.

Otherwise, note that every "00" or "10" conversion allows a '0' to effectively "move" to the right until only one '0' remains once all operations are optimally applied. Specifically:

  1. Find the index of the first '0'. Let this be idx.
  2. Count the total number of '0's in the string (let this be countZero).
  3. The maximum binary string obtainable is formed as:
    • The prefix from the start to idx remains unchanged (all '1's).
    • Then, we add (countZero - 1) '1's.
    • Insert a single '0'.
    • Finally, append the remaining characters by filling with '1's for the rest of the string.

Thus, the final string becomes: prefix + "1"(countZero - 1) + "0" + "1"(remainingLength) where remainingLength = totalLength - idx - countZero.

This approach uses simple arithmetic and string manipulation, making it both efficient and straightforward.

Code Solutions

# Python Solution

def maximumBinaryString(binary: str) -> str:
    # If the string contains at most one '0', no transformation increases its value.
    if binary.count('0') < 2:
        return binary
    
    # Find the index of the first occurrence of '0'
    first_zero_index = binary.find('0')
    
    # Count the total number of zeros in the string
    total_zero_count = binary.count('0')
    
    # Build the final string:
    # - The part before the first '0' remains unchanged.
    # - The next (total_zero_count - 1) characters become '1'.
    # - Insert a single '0'.
    # - The remainder of the string (if any) are all '1's.
    prefix = binary[:first_zero_index]
    ones_middle = "1" * (total_zero_count - 1)
    ones_suffix = "1" * (len(binary) - first_zero_index - total_zero_count)
    
    return prefix + ones_middle + "0" + ones_suffix

# Example usage:
print(maximumBinaryString("000110"))  # Expected output: "111011"
print(maximumBinaryString("01"))      # Expected output: "01"
← Back to All Questions