Maximum Binary String After Change

Medium
1223.

Maximum Binary String After Change

Maximum Binary String After Change is a medium coding problem on strings and greedy, asked in Amazon and Google interviews.

You are given a binary string binary. You may apply the following operations any number of times, in any order:

  • replace a substring "00" with "10";
  • replace a substring "10" with "01".

Return the largest binary string you can obtain, comparing strings as binary numbers (the length never changes, so this is the same as lexicographic order).

Example 1

Input
binary = "0101"
Output
1011
Explanation
`0101 → 0011 → 1011` (`10→01`, then `00→10`).

Example 2

Input
binary = "1000"
Output
1110

Example 3

Input
binary = "11"
Output
11
Explanation
No operation applies.

Constraints

  • 1 <= binary.length <= 10^5
  • binary[i] is '0' or '1'
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} binary
 * @return {string}
 */
var maximumBinaryString = function(binary) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Binary String After Change — Problem & Solution

Maximum Binary String After Change solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Maximum Binary String After Change is a medium coding problem on strings and greedy, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Strings, Greedy
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given a binary string binary. You may apply the following operations any number of times, in any order:

  • replace a substring "00" with "10";
  • replace a substring "10" with "01".

Return the largest binary string you can obtain, comparing strings as binary numbers (the length never changes, so this is the same as lexicographic order).

Example 1

Input: binary = "0101"
Output: 1011
Explanation: `0101 → 0011 → 1011` (`10→01`, then `00→10`).

Example 2

Input: binary = "1000"
Output: 1110

Example 3

Input: binary = "11"
Output: 11
Explanation: No operation applies.

Constraints

  • 1 <= binary.length <= 10^5
  • binary[i] is '0' or '1'

Hints for Maximum Binary String After Change

  1. Hint 1

    Ones before the first zero are already as good as they can be — leave them.

  2. Hint 2

    The 10 → 01 move lets you slide a zero leftwards past ones, so all zeros can be gathered into one block right after that prefix.

  3. Hint 3

    A block of z zeros becomes z − 1 ones followed by one zero using 00 → 10. So at most one zero survives.

How to solve Maximum Binary String After Change

Every zero after the first one can be pulled left next to it, and a block of zeros collapses to ones with a single 0 at its end — so the answer has exactly one zero (if there were at least two), at position firstZero + zeros − 1.

Approach

  1. Count the zeros z. If z <= 1, return the string unchanged.
  2. Let p be the index of the first zero.
  3. Return a string of all 1s except a 0 at index p + z − 1.

Why it works

Reachable: 10 → 01 slides each later zero left past ones until all z zeros sit at p … p + z − 1, and 00 → 10 applied from the left of that block turns it into z − 1 ones and a final zero. Optimal: for a string with at least one zero let f = (index of its first zero) + (number of zeros) − 1. 10 → 01 keeps the zero count and never moves the first zero right, and 00 → 10 removes one zero while moving the first zero right by at most one, so f never increases and every reachable string has f ≤ p + z − 1. A reachable string's first zero is therefore at an index ≤ p + z − 1, with equality only if it has a single zero — so it is never larger than the string of ones with one zero at p + z − 1.

Complexity

  • Time — O(n)
  • Space — O(n) for the output

Pitfalls

  • Strings with zero or one 0 cannot be improved at all.
  • The surviving zero is not at the end of the string — ones after the zero block stay where they are.
  • Simulating the operations is exponential; count instead.

Reference solution

Python

def maximumBinaryString(binary: str) -> str:
    zeros = binary.count("0")
    if zeros <= 1:
        return binary
    pos = binary.index("0") + zeros - 1
    n = len(binary)
    return "1" * pos + "0" + "1" * (n - pos - 1)

Java

public static String maximumBinaryString(String binary) {
    int n = binary.length(), zeros = 0, first = -1;
    for (int i = 0; i < n; i++) {
        if (binary.charAt(i) == '0') {
            zeros++;
            if (first < 0) first = i;
        }
    }
    if (zeros <= 1) return binary;
    char[] res = new char[n];
    Arrays.fill(res, '1');
    res[first + zeros - 1] = '0';
    return new String(res);
}

C++

string maximumBinaryString(string binary) {
    int n = (int)binary.size(), zeros = 0, first = -1;
    for (int i = 0; i < n; i++) {
        if (binary[i] == '0') {
            zeros++;
            if (first < 0) first = i;
        }
    }
    if (zeros <= 1) return binary;
    string res(n, '1');
    res[first + zeros - 1] = '0';
    return res;
}

JavaScript

var maximumBinaryString = function(binary) {
    var n = binary.length, zeros = 0, first = -1;
    for (var i = 0; i < n; i++) {
        if (binary[i] === "0") {
            zeros++;
            if (first < 0) first = i;
        }
    }
    if (zeros <= 1) return binary;
    var pos = first + zeros - 1;
    var out = [];
    for (var j = 0; j < n; j++) out.push(j === pos ? "0" : "1");
    return out.join("");
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Greedy Algorithms