Formatted question description: https://leetcode.ca/all/1702.html

# 1702. Maximum Binary String After Change (Medium)

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"`

.- For example,
`"`

"__00__010" -> "__10__010

- For example,
- Operation 2: If the number contains the substring
`"10"`

, you can replace it with`"01"`

.- For example,
`"000`

__10__" -> "000__01__"

- For example,

*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 <= 10`

^{5}`binary`

consist of`'0'`

and`'1'`

.

**Related Topics**:

Greedy

## Solution 1. Greedy

For leading `00`

, we always replace it with `10`

.

For pattern `01...10`

(`1`

s surrounded by `0`

s), we always replace it with `101...1`

.

If we repeat this pattern replacement, we will eventually only get a single `0`

in the answer, and the index of this `0`

is `first + zero - 1`

, where `first`

is the index of the first occurrence of `0`

and `zero`

is the count of `0`

s.

```
// OJ: https://leetcode.com/problems/maximum-binary-string-after-change/
// Time: O(N)
// Space: O(1)
class Solution {
public:
string maximumBinaryString(string s) {
int N = s.size(), zero = 0, first = -1;
for (int i = 0; i < N; ++i) {
if (s[i] == '0') {
++zero;
if (first == -1) first = i;
}
s[i] = '1';
}
if (first != -1) s[first + zero - 1] = '0';
return s;
}
};
```

Java

```
class Solution {
public String maximumBinaryString(String binary) {
Deque<Integer> deque = new LinkedList<Integer>();
int length = binary.length();
for (int i = 0; i < length; i++) {
if (binary.charAt(i) == '0')
deque.offerLast(i);
}
while (deque.size() >= 2) {
int index = deque.pollFirst();
deque.pollFirst();
deque.offerFirst(index + 1);
}
char[] array = new char[length];
Arrays.fill(array, '1');
while (!deque.isEmpty())
array[deque.pollFirst()] = '0';
return new String(array);
}
}
```