LeetCode Problem 1702

Difficulty: 🟡 Medium
Topics: String, Greedy

Solution

LeetCode 1702, Maximum Binary String After Change

Problem Understanding

This problem gives us a binary string consisting only of '0' and '1'. We are allowed to repeatedly apply two transformation rules:

• Replace "00" with "10"
• Replace "10" with "01"

We may perform these operations as many times as we want, in any order, and the goal is to produce the numerically largest possible binary string.

Since binary numbers are compared by their decimal value, maximizing the string means we want the leftmost bits to be as large as possible. In practice, this means we want as many leading '1' characters as possible.

The input length can be as large as 10^5, which immediately tells us that exponential exploration or repeated simulation of all possible transformations is infeasible. We need a linear or near linear solution.

The most important observation is that these operations allow zeros to move and combine in a very particular way. A naive implementation might repeatedly scan the string and apply transformations until no more changes are possible, but this would be far too slow for large inputs.

Several edge cases are important:

• Strings containing no zeros, such as "1111", are already maximal.
• Strings containing exactly one zero, such as "10111", cannot eliminate that zero entirely.
• Strings like "0000" can be transformed significantly, and understanding the final arrangement is critical.
• Very short strings such as "0" or "01" must still work correctly.
• Multiple separated zeros eventually collapse into a single zero in the optimal result.

The problem guarantees that the input contains only valid binary characters and that the string length is at least 1.

Approaches

Brute Force Approach

A brute force solution would repeatedly apply all possible operations until no further improvement is possible.

One way to do this is:

1. Scan the string for occurrences of "00" and replace them with "10".
2. Scan for occurrences of "10" and replace them with "01".
3. Continue until the string stabilizes.

This approach is correct because it directly follows the allowed operations and explores transformations toward larger binary values.

However, the problem is that each transformation changes only a small part of the string. In the worst case, we may perform a huge number of operations. For a string of length n, the number of transformations can approach O(n^2). Since n can be 100000, this becomes too slow.

Optimal Greedy Observation

The key insight is that all zeros except one can eventually be converted into ones.

The operations effectively allow zeros to move to the right while turning earlier positions into ones.

Consider what happens:

• "00" -> "10" reduces the number of zeros by one.
• "10" -> "01" moves a zero to the right.

Eventually:

• All zeros merge into a single remaining zero.
• That zero ends up in a predictable position.

Suppose:

• first_zero is the index of the first '0'
• zero_count is the total number of zeros

Then the final string will contain:

• All '1'
• Except for exactly one '0'
• Located at index:

first_zero + zero_count - 1

Why?

Every zero after the first can effectively be transformed into a '1', while the remaining zero gets pushed rightward by the transformations.

This gives us a direct construction algorithm in linear time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Simulates repeated transformations
Optimal	O(n)	O(n)	Directly constructs final maximal string

Algorithm Walkthrough

1. Scan the string to locate the first occurrence of '0'.

If no zero exists, the string is already maximal because all bits are '1'. 2. Count the total number of zeros in the string.

This tells us how many zeros can eventually be merged together. 3. Compute the final position of the remaining zero.

The remaining zero will end up at:

first_zero + zero_count - 1

This happens because each additional zero effectively shifts the surviving zero one position to the right. 4. Create a result array filled entirely with '1'.

Since the optimal string contains only one zero, every other position should be '1'. 5. Place a single '0' at the computed index.

This constructs the maximal achievable binary string directly. 6. Convert the array back into a string and return it.

Why it works

The crucial invariant is that the operations never increase the number of zeros. Operation "00" -> "10" decreases the zero count by one, while "10" -> "01" preserves it but moves a zero to the right.

Because zeros can always be shifted rightward and merged together, the optimal configuration is the one where exactly one zero remains and is pushed as far right as possible without violating the transformation rules. The derived index first_zero + zero_count - 1 is precisely where that remaining zero must end up.

Python Solution

class Solution:
    def maximumBinaryString(self, binary: str) -> str:
        first_zero = binary.find('0')

        if first_zero == -1:
            return binary

        zero_count = binary.count('0')

        result = ['1'] * len(binary)

        remaining_zero_index = first_zero + zero_count - 1
        result[remaining_zero_index] = '0'

        return ''.join(result)

The implementation begins by finding the first zero in the string. If no zero exists, the input is already optimal, so we immediately return it.

Next, we count how many zeros exist overall. This determines how far the surviving zero will be shifted to the right.

We then construct a result array containing only '1' characters. Since the optimal final state contains exactly one zero, we compute its final position using:

first_zero + zero_count - 1

Finally, we place the zero at that position and join the array into the final string.

The implementation is concise because the greedy observation eliminates the need for explicit simulation.

Go Solution

func maximumBinaryString(binary string) string {
    firstZero := -1
    zeroCount := 0

    for i := 0; i < len(binary); i++ {
        if binary[i] == '0' {
            zeroCount++

            if firstZero == -1 {
                firstZero = i
            }
        }
    }

    if firstZero == -1 {
        return binary
    }

    result := make([]byte, len(binary))

    for i := 0; i < len(binary); i++ {
        result[i] = '1'
    }

    remainingZeroIndex := firstZero + zeroCount - 1
    result[remainingZeroIndex] = '0'

    return string(result)
}

The Go implementation follows exactly the same logic as the Python solution.

One difference is that Go strings are immutable, so we use a []byte slice to construct the result efficiently. After modifying the slice, we convert it back into a string.

No integer overflow concerns exist because indices remain within the bounds of the string length, which is at most 10^5.

Worked Examples

Example 1

Input:

binary = "000110"

Step 1: Find the first zero

Index	Character
0	0

So:

first_zero = 0

Step 2: Count zeros

The string contains four zeros.

zero_count = 4

Step 3: Compute remaining zero position

remaining_zero_index = 0 + 4 - 1 = 3

Step 4: Build result

Start with all ones:

111111

Place zero at index 3:

111011

Final answer:

"111011"

Example 2

Input:

binary = "01"

Step 1: Find the first zero

first_zero = 0

Step 2: Count zeros

zero_count = 1

Step 3: Compute remaining zero position

remaining_zero_index = 0 + 1 - 1 = 0

Step 4: Build result

Start with:

11

Place zero at index 0:

01

Final answer:

"01"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	One pass to find zeros, one pass to build result
Space	O(n)	Result array requires linear extra space

The algorithm performs only a constant number of linear scans across the input string. No nested loops or repeated simulations occur. Because we construct a new result array, the space usage is linear in the input size.

Test Cases

solution = Solution()

assert solution.maximumBinaryString("000110") == "111011"  # provided example
assert solution.maximumBinaryString("01") == "01"  # provided example
assert solution.maximumBinaryString("1") == "1"  # single one
assert solution.maximumBinaryString("0") == "0"  # single zero
assert solution.maximumBinaryString("11") == "11"  # already maximal
assert solution.maximumBinaryString("00") == "10"  # simplest merge
assert solution.maximumBinaryString("0000") == "1110"  # all zeros
assert solution.maximumBinaryString("1001") == "1101"  # separated zeros
assert solution.maximumBinaryString("101010") == "111001"  # alternating pattern
assert solution.maximumBinaryString("1110111") == "1110111"  # exactly one zero
assert solution.maximumBinaryString("001") == "101"  # leading zeros
assert solution.maximumBinaryString("010101") == "111001"  # multiple movable zeros

Test	Why
"000110"	Validates the primary example
"01"	Validates minimal movable case
"1"	Single character without zeros
"0"	Single character with zero
"11"	Already optimal string
"00"	Smallest reducible case
"0000"	All zeros collapse into one
"1001"	Zeros separated by ones
"101010"	Alternating pattern stress test
"1110111"	Exactly one zero remains unchanged
"001"	Leading zeros
"010101"	Multiple transformations required

Edge Cases

One important edge case occurs when the string contains no zeros at all, such as "11111". A buggy implementation might incorrectly attempt to place a zero somewhere in the result. The correct behavior is to immediately return the original string unchanged. The implementation handles this by checking whether first_zero == -1.

Another critical case is when the string contains exactly one zero, such as "10111". Since no "00" pair exists, the number of zeros cannot be reduced further. The optimal string therefore still contains exactly one zero in the same effective position. The formula naturally handles this because zero_count - 1 becomes zero.

A third important edge case is a string made entirely of zeros, such as "00000". A naive simulation may become inefficient because many operations are possible. The greedy construction correctly recognizes that all zeros eventually collapse into one remaining zero near the end of the string. The final output becomes "11110".

Another subtle case involves zeros separated by many ones, such as "100001". The operations allow zeros to move and merge across the string, so the final arrangement is not obvious from the original positions. The mathematical placement formula ensures the remaining zero lands exactly where it should regardless of spacing.