Skip to main content

1702. Maximum Binary String After Change

medium

Apply 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 Sam K., 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^5
  • binary consist of '0' and '1'.

Examples

Example 1

Input
binary = "000110"
Output
"111011"

Explanation: A valid transformation sequence can be: "000110" -> "000101" -> "100101" -> "110101" -> "110011" -> "111011"

Example 2

Input
binary = "01"
Output
"01"

Explanation: Cannot apply any operation.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

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

More Bit Manipulation practice problems

See all Bit Manipulation problems →