Maximum Binary String After Change: Greedy Pattern

You are given a binary string binary consisting of '0's and '1's. You can apply two operations any number of times in any order:

• Operation 1: If the string contains "00", you can replace it with "10".
• Operation 2: If the string contains "10", you can replace it with "01".

Return the maximum binary string you can get after applying these operations. A binary string x is greater than y if the decimal value of x is greater than the decimal value of y.

This is LeetCode 1702: Maximum Binary String After Change, a medium problem that tests your ability to see through operational complexity to a clean greedy structure. The two operations look like they open up a huge search space, but the optimal answer always has the same simple form.

Why this problem matters

Maximum Binary String After Change is a great example of a problem where simulation would be painfully slow, but understanding what the operations actually achieve gives you a direct formula. The two operations together let you slide ones to the right past zeros (Operation 2 turns "10" into "01", swapping a one-zero pair) and convert any pair of adjacent zeros into "10" (Operation 1). Those two primitives are all you need.

This pattern of "understand what the operations allow, then jump to the answer" shows up in many greedy and math problems. Instead of simulating every possible sequence of moves, you figure out the reachable end state and construct it directly.

The key insight

Leading 1s never need to change. They are already as large as possible in their positions. So skip them.

After the first zero, count how many zeros exist in the rest of the string. Using Operation 2, you can slide all those zeros together into a contiguous block. Then using Operation 1, you convert pairs of zeros into "10", each time consuming one zero and producing a one.

If you have z zeros, you can convert z - 1 pairs (each pair shares one zero with the next), leaving exactly one zero behind. That single remaining zero sits at position first_zero_index + z - 1. Every other position becomes a 1.

The result is always: all 1s, except for a single 0 at one specific position. The formula places that zero at the earliest spot it can possibly end up, and every other bit becomes a 1.

The solution

def maximumBinaryString(binary):
    n = len(binary)
    first_zero = -1
    zeros = 0

    for i in range(n):
        if binary[i] == '0':
            if first_zero == -1:
                first_zero = i
            zeros += 1

    if zeros == 0:
        return binary

    result = ['1'] * n
    result[first_zero + zeros - 1] = '0'
    return ''.join(result)

One pass to gather information, then construct the answer directly. Here is what each piece does:

1. Scan the string to find the index of the first '0' and count the total number of zeros.
2. If there are no zeros, the string is already all 1s, which is the maximum. Return it as-is.
3. Build a result of all 1s. Place the single remaining '0' at position first_zero + zeros - 1. This is where the last zero ends up after all conversions.
4. Return the result.

Visual walkthrough

Complexity analysis

This is optimal. You must read every character to know where the zeros are, so O(n) is the lower bound for time. The output itself is n characters, so O(n) space is unavoidable.

The building blocks

This problem is built on 2 reusable patterns that CodeBricks drills independently.

1. Operation reduction

Instead of simulating individual operations, analyze what the full set of operations can achieve. Operation 2 lets you slide ones rightward past zeros (swapping each "10" pair into "01"). Operation 1 lets you convert a pair of adjacent zeros into a one plus a zero. Together, they let you consolidate all zeros and convert all but one.

for i in range(n):
    if condition(s[i]):
        count += 1
        if first_occurrence == -1:
            first_occurrence = i

This pattern of scanning for a first occurrence and counting total matches shows up in problems like First Missing Positive, Move Zeroes, and any problem where you need to know both where something starts and how many there are.

2. Direct construction from invariants

Once you know the structure of the optimal answer (all 1s with exactly one 0 at a computed position), you build it directly rather than transforming the input step by step.

result = [default_value] * n
result[computed_position] = special_value

This "construct from formula" pattern appears in problems like Product of Array Except Self, where instead of simulating, you compute the answer from prefix and suffix information. The key is recognizing when the answer has a predictable structure.

Edge cases

Before submitting, make sure your solution handles these:

• All ones "1111": no zeros to convert. Return the input unchanged.
• All zeros "0000": four zeros, first at index 0. Position of remaining zero: 0 + 4 - 1 = 3. Result: "1110".
• Single character "0" or "1": only one character, so no pair of characters exists for either operation. Return as-is.
• Leading zeros "0010": first zero at index 0, three zeros total. Remaining zero at 0 + 3 - 1 = 2. Result: "1101".
• One zero at the end "1110": first zero at index 3, one zero total. Remaining zero at 3 + 1 - 1 = 3. Result: "1110" (unchanged, already maximum).
• Zeros scattered throughout "10101": first zero at index 1, two zeros total. Remaining zero at 1 + 2 - 1 = 2. Result: "11011".

From understanding to recall

You have read the solution and it makes sense. Count zeros, find the first one, place the lone remaining zero at the right position. Clean. But can you reproduce the formula first_zero + zeros - 1 under interview pressure without second-guessing yourself?

The tricky part is convincing yourself that the two operations truly allow you to consolidate all zeros and convert all but one. Walking through a few examples helps, but what really locks it in is writing the solution from scratch multiple times at spaced intervals. After a few rounds, you see "binary string operations" and the pattern clicks immediately: skip leading ones, count zeros, compute the position.

The operation reduction and direct construction patterns are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping they stick.

Related posts

• String Without AAA or BBB - Greedy character scheduling where you build the answer one piece at a time
• Orderly Queue - Another problem where understanding what operations allow eliminates the need for simulation
• Flip String to Monotone Increasing - Binary string transformation with a single-pass counting approach

CodeBricks breaks the maximum binary string after change LeetCode problem into its operation reduction and direct construction building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a binary string transformation question shows up in your interview, you do not think about it. You just write it.