1702. Maximum Binary String After Change
mediumApply two binary-string operations to maximize the resulting value: 00 → 10 and 10 → 01. The greedy insight: every operation reduces the count of zeros by one but cascades them left.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
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". Operation 2: If the number contains the substring "10", you can replace it with "01". 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.
Constraints
1 <= binary.length <= 10^5binary consist of '0' and '1'.
Examples
Example 1
binary = "000110""111011"Explanation: A valid transformation sequence can be: "000110" -> "000101" -> "100101" -> "110101" -> "110011" -> "111011"
Example 2
binary = "01""01"Explanation: Cannot apply any operation.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
Hints
Progressive — try the first before opening the next.
Hint 1
Leading 1s never decrease the value and can be left alone — skip the initial run of 1s.
Hint 2
After that prefix, the answer has the form 1...1 0 1...1 — a single 0 buried among 1s.
Hint 3
Position of that single 0 = first_zero + (number_of_zeros - 1). Count the zeros and the index of the first zero in the remaining suffix.
Hint 4
Construct the answer directly without simulating: fill with 1s, place a single 0 at the computed position.
Solution approach
Reveal approach
Greedy construction. Find prefix_ones = the count of leading 1s. If prefix_ones == n, the input is already all 1s — return it. Otherwise, count zeros = number of '0's in binary[prefix_ones..n-1]. The output starts with prefix_ones 1s, then n - prefix_ones - zeros = remaining 1s, but more cleanly: the final answer is a string of all 1s with a single 0 at position prefix_ones + (zeros - 1). Build a char array of n 1s, set position[prefix_ones + zeros - 1] to '0', and return. O(n) time, O(n) output space. The key insight is that operations 1 and 2 together act like 'shift any zero leftward, consuming an adjacent zero on the way' — so all zeros eventually collapse into a single zero whose position is determined by the original first-zero index plus the number of zeros minus one.
Complexity
- Time
- O(n)
- Space
- O(n) output
Related patterns
- greedy
- string
Asked at
Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).
- Amazon
Practice these live with InterviewChamp.AI
Drill Maximum Binary String After Change and Bit Manipulation problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →