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:
"00", you can replace it with "10".
"00010" -> "10010""10", you can replace it with "01".
"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 <= 105binary consist of '0' and '1'.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.
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'.
Python
C++
Java
JavaScript
C#
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.
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.
Python
C++
Java
JavaScript
C#
Time Complexity: O(n), with ample optimization from two passes over the string.
Space Complexity: O(n), reconstructs the string twice.
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.
| 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 | — |
| 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. |
Biweekly Contest 42 | Number of Students Unable to Eat Lunch | Maximum Binary String After Change • code Explainer • 3,409 views views
Watch 6 more video solutions →Practice Maximum Binary String After Change with our built-in code editor and test cases.
Practice on FleetCode