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^5binary[i] is '0' or '1'
Hints for Maximum Binary String After Change
Hint 1
Ones before the first zero are already as good as they can be — leave them.
Hint 2
The
10 → 01move lets you slide a zero leftwards past ones, so all zeros can be gathered into one block right after that prefix.Hint 3
A block of
zzeros becomesz − 1ones followed by one zero using00 → 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
- Count the zeros
z. Ifz <= 1, return the string unchanged. - Let
pbe the index of the first zero. - Return a string of all
1s except a0at indexp + 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
0cannot 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