Maximum Binary String After Change solution and explanation
7 more videos on this problem
Biweekly Contest 42 | Number of Students Unable to Eat Lunch | Maximum Binary String After Changecode Explainer · 24:19 · 3K views
Leetcode 1702. Maximum Binary String After ChangeFraz · 10:36 · 3K views
1702. Maximum Binary String After Change (Leetcode Medium)Programming Live with Larry · 17:33 · 472 views
【每日一题】1702. Maximum Binary String After Change, 12/26/2020Huifeng Guan · 18:41 · 343 views
Leetcode 1702. Maximum Binary String After ChangeElite Code · 26:36 · 281 views
大壮刷题 - 1702. Maximum Binary String After Change, Medium, Greedy大壮刷题 · 9:49 · 66 views
LeetCode 1702: Maximum Binary String After ChangeAlitaCode · 28:38
Software Engineering: (Algorithm) Maximum Binary String After Making Changes (2 Solutions!!)Roel Van de Paar · 2:05 · 12 views
The problem
You are given a binary string binary consisting of only 0's or 1's. You can apply each of the following operations any number of times:
- Operation 1: If the number contains the substring
"00", you can replace it with"10".- For example,
"00010" -> "10010"
- For example,
- Operation 2: If the number contains the substring
"10", you can replace it with"01".- For example,
"00010" -> "00001"
- For example,
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.
Example 1:
Input: binary = "000110" Output: "111011" Explanation: A valid transformation sequence can be: "000110" -> "000101" "000101" -> "100101" "100101" -> "110101" "110101" -> "110011" "110011" -> "111011"
Example 2:
Input: binary = "01" Output: "01" Explanation: "01" cannot be transformed any further.
Constraints:
1 <= binary.length <= 105binaryconsist of'0'and'1'.
Approach overview
Problem Overview: You are given a binary string and two allowed operations that move or merge zeros: "00" → "10" and "10" → "01". Apply any number of operations to produce the lexicographically largest possible binary string.
Approach 1: Direct Simulation (O(n^2) time, O(n) space)
This method simulates the allowed operations exactly as defined. You scan the string looking for patterns "00" or "10" and replace them accordingly. Each operation gradually pushes zeros to the right while converting earlier positions into '1'. Because every modification may require rescanning or shifting characters, the process can degrade to quadratic time in the worst case. This approach helps build intuition about how zeros migrate through the string and why eventually almost all characters become '1'.
Approach 2: Two-Pointer Greedy Insight (O(n) time, O(1) space)
The operations effectively guarantee that all zeros collapse into a single position. After repeatedly applying the rules, the final string becomes all '1' except for one '0'. The position of that zero depends on two values: the index of the first zero and the total number of zeros. If the first zero appears at index i and there are k zeros, the final zero ends up at position i + k - 1. You count zeros with a single pass and rebuild the result string with '1' everywhere except that index. A two-pointer or linear scan works well here since you only track the first zero and total zero count. This greedy observation removes the need to simulate operations and gives a clean linear solution.
The reasoning relies on how the operations always move zeros rightward while turning earlier digits into ones. Eventually every zero except one can be absorbed by earlier transformations.
Recommended for interviews: The greedy counting approach using a single pass is what interviewers expect. It demonstrates that you recognized the invariant created by the operations instead of simulating them. Implementing the direct simulation first can show understanding, but the optimal solution using a linear scan and counting zeros shows stronger algorithmic insight with concepts from greedy, string manipulation, and two pointers.
Approach 1: Approach 1: Direct Simulation
This approach simulates the process of applying operations in a strategic manner to transform the binary string into its maximum form. The operations swap '00' with '10' and '10' with '01' offer a way to push '0's towards the end of the string.
In this approach, we will iterate over the binary string and make localized swaps following the allowed operations, continuously moving '0's to form an optimal pattern at the end of the string.
def maximumBinaryString(binary):
if '0' not in binary:
return binary
zero_count = binary.count('0') # Total number of '0's
first_zero = binary.index('0') # Index of first occurrence of '0'
max_transformation = '1' * first_zero + '0' * (zero_count - 1) + '1' * (len(binary) - first_zero - zero_count + 1)
return max_transformation
# Test
print(maximumBinaryString("000110")) # Output: "111011"public class Solution {
public String maximumBinaryString(String binary) {
int zeroCount = 0, firstZeroIndex = -1;
int n = binary.length();
for (int i = 0; i < n; i++) {
if (binary.charAt(i) == '0') {
if (firstZeroIndex == -1) firstZeroIndex = i;
zeroCount++;
}
}
if (zeroCount == 0) return binary;
StringBuilder sb = new StringBuilder();
sb.append("1".repeat(firstZeroIndex));
sb.append("0");
sb.append("1".repeat(n - firstZeroIndex - zeroCount));
return sb.toString();
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.maximumBinaryString("000110")); // Output: "111011"
}
}#include <iostream>
#include <string>
using namespace std;
string maximumBinaryString(string binary) {
int zeroCount = 0, firstZeroIndex = -1;
for (int i = 0; i < binary.length(); ++i) {
if (binary[i] == '0') {
if (firstZeroIndex == -1) firstZeroIndex = i;
zeroCount++;
}
}
if (zeroCount == 0) return binary;
return string(firstZeroIndex, '1') + string(zeroCount - 1, '0') + string(binary.length() - firstZeroIndex - zeroCount + 1, '1');
}
int main() {
cout << maximumBinaryString("000110") << endl; // Output: "111011"
return 0;
}function maximumBinaryString(binary) {
let zeroCount = 0, firstZeroIndex = -1;
const n = binary.length;
for (let i = 0; i < n; i++) {
if (binary[i] === '0') {
if (firstZeroIndex === -1) firstZeroIndex = i;
zeroCount++;
}
}
if (zeroCount === 0) return binary;
return '1'.repeat(firstZeroIndex) + '0' + '1'.repeat(n - firstZeroIndex - zeroCount);
}
console.log(maximumBinaryString("000110")); // Output: "111011"public class Solution {
public string MaximumBinaryString(string binary) {
int zeroCount = 0, firstZeroIndex = -1;
int n = binary.Length;
for (int i = 0; i < n; i++) {
if (binary[i] == '0') {
if (firstZeroIndex == -1) firstZeroIndex = i;
zeroCount++;
}
}
if (zeroCount == 0) return binary;
return new string('1', firstZeroIndex) + "0" + new string('1', n - firstZeroIndex - zeroCount);
}
public static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.MaximumBinaryString("000110")); // Output: "111011"
}
}This Python solution counts the number of '0's and determines the index of the first '0'. It then forms the maximum binary string by placing as many '1's before the first zero index followed by all but one '0', and filling the remaining positions with '1'.
Time Complexity: O(n), where n is the length of the string, due to counting and constructing the string.
Space Complexity: O(1), no significant additional space usage besides the input and some variables.
Approach 2: Approach 2: Using Two-Pointer Technique
This approach utilizes a two-pointer technique to rearrange the string iteratively. The goal is to move all '0's towards the end of the string while keeping track of the maximum possible configuration of '1's preceding them and avoiding conflicts where '00' patterns may persist by restructuring effectively using both operations strategically.
def maximumBinaryString(binary):
i = 0
while i < len(binary) - 1:
if binary[i] == '0' and binary[i + 1] == '0':
binary = binary[:i] + '1' + '0' + binary[i + 2:]
i += 1
i += 1
i = 0
j = 1
binary = list(binary)
while i < len(binary) and j < len(binary):
if binary[i] == '1' and binary[j] == '0':
binary[i], binary[j] = binary[j], binary[i]
i += 1
j += 1
return ''.join(binary)
print(maximumBinaryString("000110")) # Output: "111011"public class Solution {
public String maximumBinaryString(String binary) {
char[] arr = binary.toCharArray();
int i = 0;
while (i < arr.length - 1) {
if (arr[i] == '0' && arr[i + 1] == '0') {
arr[i] = '1';
arr[i + 1] = '0';
i++;
}
i++;
}
i = 0;
int j = 1;
while (i < arr.length && j < arr.length) {
if (arr[i] == '1' && arr[j] == '0') {
char temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
}
j++;
}
return new String(arr);
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.maximumBinaryString("000110")); // Output: "111011"
}
}#include <iostream>
#include <string>
using namespace std;
string maximumBinaryString(string binary) {
int i = 0;
while (i < binary.size() - 1) {
if (binary[i] == '0' && binary[i + 1] == '0') {
binary[i] = '1';
binary[i + 1] = '0';
i++;
}
i++;
}
i = 0;
int j = 1;
while (i < binary.size() && j < binary.size()) {
if (binary[i] == '1' && binary[j] == '0') {
swap(binary[i], binary[j]);
i++;
}
j++;
}
return binary;
}
int main() {
cout << maximumBinaryString("000110") << endl; // Output: "111011"
return 0;
}function maximumBinaryString(binary) {
let arr = binary.split('');
let i = 0;
while (i < arr.length - 1) {
if (arr[i] === '0' && arr[i + 1] === '0') {
arr[i] = '1';
arr[i + 1] = '0';
i++;
}
i++;
}
i = 0;
let j = 1;
while (i < arr.length && j < arr.length) {
if (arr[i] === '1' && arr[j] === '0') {
[arr[i], arr[j]] = [arr[j], arr[i]];
i++;
}
j++;
}
return arr.join('');
}
console.log(maximumBinaryString("000110")); // Output: "111011"public class Solution {
public string MaximumBinaryString(string binary) {
char[] arr = binary.ToCharArray();
int i = 0;
while (i < arr.Length - 1) {
if (arr[i] == '0' && arr[i + 1] == '0') {
arr[i] = '1';
arr[i + 1] = '0';
i++;
}
i++;
}
i = 0;
int j = 1;
while (i < arr.Length && j < arr.Length) {
if (arr[i] == '1' && arr[j] == '0') {
char temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
}
j++;
}
return new string(arr);
}
public static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.MaximumBinaryString("000110")); // Output: "111011"
}
}This Python solution employs a two-pointer strategy to iteratively fix adjacent '0' pairs to '10' first and then uses another pass to align remaining lone '0's to minimize their impact, forming the maximum binary layout.
Time Complexity: O(n), with ample optimization from two passes over the string.
Space Complexity: O(n), reconstructs the string twice.
Approach 3: Quick Thinking
We observe that operation 2 can move all 1s to the end of the string, and operation 1 can change all 0000..000 strings to 111..110.
Therefore, to get the maximum binary string, we should move all 1s that are not at the beginning to the end of the string, making the string in the form of 111..11...000..00..11. Then, with the help of operation 1, we change the middle 000..00 to 111..10. In this way, we can finally get a binary string that contains at most one 0, which is the maximum binary string we are looking for.
In the code implementation, we first judge whether the string contains 0. If it does not, we directly return the original string. Otherwise, we find the position k of the first 0, add the number of 0s after this position, and the position of 0 in the modified string is obtained. The rest of the positions are all 1s.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the string.
function maximumBinaryString(binary: string): string {
let k = binary.indexOf('0');
if (k === -1) {
return binary;
}
k += binary.slice(k + 1).split('0').length - 1;
return '1'.repeat(k) + '0' + '1'.repeat(binary.length - k - 1);
}func maximumBinaryString(binary string) string {
k := strings.IndexByte(binary, '0')
if k == -1 {
return binary
}
for _, c := range binary[k+1:] {
if c == '0' {
k++
}
}
ans := []byte(binary)
for i := range ans {
ans[i] = '1'
}
ans[k] = '0'
return string(ans)
}impl Solution {
pub fn maximum_binary_string(binary: String) -> String {
if let Some(k) = binary.find('0') {
let k = k + binary[k + 1..].chars().filter(|&c| c == '0').count();
return format!(
"{}{}{}",
"1".repeat(k),
"0",
"1".repeat(binary.len() - k - 1)
);
}
binary
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Direct Simulation | Time Complexity: O(n), where n is the length of the string, due to counting and constructing the string. |
| Approach 2: Using Two-Pointer Technique | Time Complexity: O(n), with ample optimization from two passes over the string. |
| Quick Thinking | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Simulation | O(n^2) | O(n) | Useful for understanding how the operations transform the string step‑by‑step. |
| Greedy with Two-Pointer Insight | O(n) | O(1) | Best choice for interviews and production solutions when scanning the string once. |
Frequently asked questions
Is Maximum Binary String After Change easy or hard?
The problem is rated Medium because the operations suggest simulation, but the intended solution requires recognizing a greedy pattern. Once you observe that all zeros collapse into a single position, the implementation becomes straightforward with a linear scan.
Maximum Binary String After Change Python/Java solution
In Python or Java, the efficient solution counts zeros and determines the final index of the single remaining zero. Then build a new string consisting mostly of '1' characters with one '0' placed at firstZero + zeroCount - 1. This implementation runs in O(n) time and constant extra space.
How to solve Maximum Binary String After Change in O(n)?
Scan the binary string once to locate the first '0' and count the total number of zeros. If there are no zeros, the string is already maximal. Otherwise, construct a result string filled with '1' and place a single '0' at index firstZero + zeroCount - 1. This works because the allowed operations always push zeros right while converting earlier digits into '1'.
What is the best approach for Maximum Binary String After Change?
The optimal approach uses a greedy observation with a single linear scan. Count the number of zeros and find the index of the first zero. If there are k zeros starting from index i, the final string will contain exactly one zero at position i + k - 1 and all other characters become '1'. This produces an O(n) time and O(1) space solution.
Is Maximum Binary String After Change asked at Google/Amazon/Meta?
Greedy string transformation problems like this frequently appear in interviews at large tech companies including Google, Amazon, and Meta. The question tests whether you can identify the invariant created by repeated operations and derive the final structure instead of simulating every step.
What data structure is used in Maximum Binary String After Change?
The problem primarily uses basic string manipulation and counting. No complex data structure is required. The optimal approach relies on greedy reasoning and simple integer tracking of the first zero index and the total number of zeros.
What is the time complexity of Maximum Binary String After Change?
The optimal greedy solution runs in O(n) time because the string is scanned once to count zeros and find the first zero. The result string is constructed in another linear pass. Space complexity is O(1) if the output string is built directly without extra structures.