Biggest Binary String After Rewrites

Medium

You are given a string bits made of 0 and 1. As many times as you like and in any order, you may apply two rewrites: - find a pair 00 and replace it with 10; - find a pair 10 and replace it with 01. Read the string as a binary number. Return the string you get when that number is made as large as possible. The rewrites never change the length of the string.

Example 1

bits="0110010" → '1110111'

Slide the zeros left towards each other (10 → 01) until they stand together: 0000111. Then apply 00 → 10 three times: 1000111 → 1100111 → 1110111.

Example 2

bits="1011" → '1011'

There is a single zero, and the only possible move, 10 → 01, would make the number smaller. The string stays as it is.

Example 3

bits="111" → '111'

Constraints

1 ≤ len(bits) ≤ 10⁵
bits contains only 0 and 1

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy String

Similar problems

Biggest Number From Pieces Medium Every Letter Once Medium Erase Digits for the Smallest Number Medium Smallest Up-Down Sequence Medium Ring of Flippable Words Medium

Input

bits="0110010"

Expected

'1110111'

Run checks the first 3 tests in your browser. Submit checks all 136 tests on the server, hidden ones included.