Maximum Binary String After Change - Practice Coding Problems

Maximum Binary String After Change - Problem

String Greedy Medium

You are given a binary string binary consisting of only 0's and 1's. You can apply each of the following operations any number of times:

Operation 1: If the string contains the substring "00", you can replace it with "10".
For example, "00010" → "10010"

Operation 2: If the string contains the substring "10", you can replace it with "01".
For example, "00010" → "00001"

Return the maximum binary string you can obtain after any number of operations. Binary string x is greater than binary string y if x's decimal representation is greater than y's decimal representation.

Input & Output

Example 1 — Basic Case

$ Input: binary = "000110"

› Output: "111011"

💡 Note: Apply operations: 000110 → 100110 → 110110 → 111010 → 111001. No more beneficial operations possible.

Example 2 — Single Zero

$ Input: binary = "01"

› Output: "10"

💡 Note: Direct application of Operation 2: 01 becomes 10 using the 10→01 rule in reverse.

Example 3 — No Zeros

$ Input: binary = "111"

› Output: "111"

💡 Note: String contains no zeros, so no operations can be applied. Return unchanged.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Binary string "000110" with operations available

Operations

00→10 and 10→01 can be applied repeatedly

Output

Maximum possible binary string "111011"

Key Takeaway

🎯 Key Insight: Move all zeros right except one, placed at the optimal position for maximum decimal value

Asked in

G Google 15 f Facebook 12

The key insight is that all zeros can be moved to the right using Operation 2 (10→01), except we need exactly one zero to remain for the maximum binary value. The optimal position for this zero is at first_zero_position + zero_count - 1. Best approach uses greedy strategy with Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Greedy - Pattern Recognition	O(n)	O(n)	Move all zeros to the right except one, position it optimally
Brute Force - Simulate All Operations	O(n³)	O(n)	Repeatedly apply operations until no more improvements possible

Greedy - Pattern Recognition — Algorithm Steps

Count total zeros in the string
If no zeros, return original string
If zeros exist, place exactly one 0 at the leftmost zero position
Fill remaining positions with 1's and remaining 0's at the end

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Zeros

Find total zeros and first zero position

Calculate Position

Optimal zero position = first_zero_pos + zero_count - 1

Construct Result

Fill with 1's except for one strategically placed 0

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* solution(char* binary) {
    int n = strlen(binary);
    int zeroCount = 0;
    int firstZeroPos = -1;
    
    // Count zeros and find first zero position
    for (int i = 0; i < n; i++) {
        if (binary[i] == '0') {
            zeroCount++;
            if (firstZeroPos == -1) {
                firstZeroPos = i;
            }
        }
    }
    
    char* result = (char*)malloc((n + 1) * sizeof(char));
    result[n] = '\0';
    
    if (zeroCount == 0) {
        strcpy(result, binary);
        return result;
    }
    
    // Fill with all 1's
    for (int i = 0; i < n; i++) {
        result[i] = '1';
    }
    
    // Place one 0 at optimal position
    result[firstZeroPos + zeroCount - 1] = '0';
    
    return result;
}

int main() {
    char binary[100001];
    fgets(binary, sizeof(binary), stdin);
    binary[strcspn(binary, "\n")] = 0;
    
    char* result = solution(binary);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to count zeros and construct result

✓ Linear Growth

Space Complexity

O(n)

Space for result string construction

⚡ Linearithmic Space

30.0K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy - Pattern Recognition — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler