Skip to main content
Talentd

Maximum Binary String After Change - Solution & Explanation

MediumStringGreedy20 min readAsked at: Huawei
Practice this problem

Problem Statement

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"
  • Operation 2: If the number 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.

 

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 <= 105
  • binary consist 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.

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'.

Code

PythonC++JavaJavaScriptC#

Python

C++

Java

JavaScript

C#

Complexity

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.

Try this approach in the editor →

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.

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.

Code

PythonC++JavaJavaScriptC#

Python

C++

Java

JavaScript

C#

Complexity

Time Complexity: O(n), with ample optimization from two passes over the string.
Space Complexity: O(n), reconstructs the string twice.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScriptRustC#

Python

Java

C++

Go

TypeScript

Rust

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Direct Simulation

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: Using Two-Pointer Technique

Time Complexity: O(n), with ample optimization from two passes over the string.
Space Complexity: O(n), reconstructs the string twice.

Quick Thinking—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Direct SimulationO(n^2)O(n)Useful for understanding how the operations transform the string step‑by‑step.
Greedy with Two-Pointer InsightO(n)O(1)Best choice for interviews and production solutions when scanning the string once.

Video Solution

Biweekly Contest 42 | Number of Students Unable to Eat Lunch | Maximum Binary String After Change • code Explainer • 3,409 views views

Watch 7 more video solutions →

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.

Ready to solve this problem?

Practice Maximum Binary String After Change with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Binary Subsequence Less Than or Equal to K