(Algorithm) Maximum Binary String After Making Changes

Question

I am given a binary string binary consisting of only 0's or 1's. There are two allowed operations (can be re-used any number of times):

Operation 1: If the number contains the substring "00", can replace it with "10". For example, "00010" -> "10010"

Operation 2: If the number contains the substring "10", can replace it with "01". For example, "00010" -> "00001"

What is the maximum binary string I 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.

I'm trying greedy ways to replace every "00" to "10", and don't see how to make use of "10" -> "01" path, but this breaks the input like "000110". How should I approach this problem instead?

Answer 1

Greedy sounds like a right way.

The prefix of 1s don't need any operation.

For the rest part,

(1) continuously take operation 2, making the string like 00...00011...11 (the original string changes to 11..1100...00011...11).

This always works because for any substring 01..10, the operation 2 results in 01..101 -> 01..1011 -> ... -> 0..01..1.

(2) then continuously take operation 1, making the string like 11...11011...11.

Note you don't really need implementing the operations but only count the number of 1s and 0s then constructing the resulted string as RiaD mentioned in his answer.

Answer 2

The problem with your solution: You can move some ones to the right, to create 00 and replace it with 10.

The other solution: suppose that number consists not only of 1s(has zero) i.e it has k 1s in the beginning, then zero, then (a zeroes and b ones in some order). I think answer is k+a ones, then zero, then b ones. It's easy to see why it's achievable answer by showing how to do that: you move all the ones except k first to the end using second rule, and then you apply first rule to replace all the zeroes but the last one. It's harder to see that the answer is indeed optimal.

Proof: if you have two zeros and only ones in between them, you can move the right one to the left one and get 1 instead of left one, so there's only at most one zero in the optimal answer. But you can't get all 1s (unless there were all the 1s in the beginning). So now the question is where this zero will be located. Proposed algorithm is optimal because every time you increase the number of consecutive elements in the first group of ones you lose 1 zero, so you can do that at most a times, so it will be no more than k+a ones