Problem Description

You are given a binary string binary consisting only of characters '0' and '1'. You can perform the following operation any number of times:

• Choose two consecutive characters 00 or 01 and replace them with 10 or 10 respectively.

• 1 ≤ binary.length ≤ 10⁵
• binary consists of only '0' and '1'

Thought Process

Let's first understand the operation: for every pair 00 or 01, we can turn the first 0 into 1 and the second into 0. This allows us to "push" zeros to the right, but never to the left. We want the largest lexicographical string, so we want as many 1s as possible at the start.

A brute-force approach would simulate every operation, but with a string of length up to 10⁵, that's too slow. Instead, we need to look for a pattern or invariant: after all possible moves, all zeros will be pushed as far to the right as possible, but no two zeros will ever be adjacent (as we can always convert 00 to 10).

This leads us to consider: after all moves, the string will have all 1s except possibly a single 0, and that 0 will be as far to the left as possible after the first block of 1s.

Solution Approach

Let's break down the steps to find the maximum binary string:

1. Find the first occurrence of 0 in the string. All 1s before it remain unchanged.
2. Count the total number of 0s in the string.
3. After all possible moves, all 0s except one will be converted to 1s. The remaining single 0 will be shifted as far left as possible, right after the first block of 1s.
4. Construct the result:
   • All 1s up to the first 0 (unchanged).
   • Then, as many 1s as (number of 0s - 1).
   • Insert a single 0 at the position (first zero index + number of zeros - 1).
   • Fill the rest with 1s.

We use string operations and counts because these are O(1) or O(n), making the algorithm efficient for large strings.

Example Walkthrough

Let's use the input binary = "000110":

• The first 0 is at index 0.
• Total number of 0s: 4.
• After all possible moves, all 0s except one become 1s.
• The single 0 will be at index: 0 + 4 - 1 = 3.
• So, the resulting string is:
  • First 3 positions: 1
  • Position 3: 0
  • Positions 4 and 5: 1
• Final answer: "111011"

At each step, we maximize the leading 1s and push the single 0 as far left as the rules allow.

Time and Space Complexity

Brute-force approach: Simulating each operation could take O(n²) time, as each operation only moves a 0 one step to the right.
Optimized approach:

• Finding the first 0 is O(n).
• Counting total 0s is O(n).
• Building the result string is O(n).

Summary

The key to this problem is recognizing the invariant: only one 0 can remain after all moves, and it is pushed as far left as possible. By counting zeros and finding the first one, we can construct the answer in linear time. This approach is both elegant and efficient, leveraging the problem's constraints to avoid unnecessary simulation.

Code Implementation

class Solution:
    def maximumBinaryString(self, binary: str) -> str:
        first_zero = binary.find('0')
        if first_zero == -1:
            return binary
        zero_count = binary.count('0')
        # All ones up to first zero, then (zero_count - 1) ones, one zero, rest ones
        result = (
            '1' * first_zero +
            '1' * (zero_count - 1) +
            '0' +
            '1' * (len(binary) - first_zero - zero_count)
        )
        return result
      

class Solution {
public:
    string maximumBinaryString(string binary) {
        int first_zero = binary.find('0');
        if (first_zero == string::npos)
            return binary;
        int zero_count = 0;
        for (char c : binary)
            if (c == '0') zero_count++;
        string result = string(first_zero, '1');
        result += string(zero_count - 1, '1');
        result += '0';
        result += string(binary.size() - first_zero - zero_count, '1');
        return result;
    }
};
      

class Solution {
    public String maximumBinaryString(String binary) {
        int firstZero = binary.indexOf('0');
        if (firstZero == -1) return binary;
        int zeroCount = 0;
        for (char c : binary.toCharArray())
            if (c == '0') zeroCount++;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < firstZero; i++) sb.append('1');
        for (int i = 0; i < zeroCount - 1; i++) sb.append('1');
        sb.append('0');
        for (int i = 0; i < binary.length() - firstZero - zeroCount; i++) sb.append('1');
        return sb.toString();
    }
}
      

var maximumBinaryString = function(binary) {
    let firstZero = binary.indexOf('0');
    if (firstZero === -1) return binary;
    let zeroCount = 0;
    for (let c of binary) {
        if (c === '0') zeroCount++;
    }
    let res = '';
    res += '1'.repeat(firstZero);
    res += '1'.repeat(zeroCount - 1);
    res += '0';
    res += '1'.repeat(binary.length - firstZero - zeroCount);
    return res;
};