# 1702. Maximum Binary String After Change

## Description

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, "00010" -> "10010"
• Operation 2: If the number contains the substring "10", you can replace it with "01".
• For example, "00010" -> "00001"

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 <= 105
• binary consist of '0' and '1'.

## Solutions

Solution 1: Quick Thinking

We observe that operation 2 can move all $1$s to the end of the string, and operation 1 can change all 0000..000 strings to 111..110.

Therefore, to get the maximum binary string, we should move all $1$s that are not at the beginning to the end of the string, making the string in the form of 111..11...00..11, and then use operation 1 to change the middle 000..00 to 111..10. In this way, we can finally get a binary string that contains at most one $0$, which is the maximum binary string we are looking for.

The time complexity is $O(n)$, where $n$ is the length of the string binary. Ignoring the space consumption of the answer, the space complexity is $O(1)$.

• class Solution {
public String maximumBinaryString(String binary) {
int k = binary.indexOf('0');
if (k == -1) {
return binary;
}
int n = binary.length();
for (int i = k + 1; i < n; ++i) {
if (binary.charAt(i) == '0') {
++k;
}
}
char[] ans = binary.toCharArray();
Arrays.fill(ans, '1');
ans[k] = '0';
return String.valueOf(ans);
}
}

• class Solution {
public:
string maximumBinaryString(string binary) {
int k = binary.find('0');
if (k == binary.npos) return binary;
int n = binary.size();
for (int i = k + 1; i < n; ++i) {
if (binary[i] == '0') {
++k;
}
}
return string(k, '1') + '0' + string(n - k - 1, '1');
}
};

• class Solution:
def maximumBinaryString(self, binary: str) -> str:
k = binary.find('0')
if k == -1:
return binary
k += binary[k + 1 :].count('0')
return '1' * k + '0' + '1' * (len(binary) - k - 1)


• func maximumBinaryString(binary string) string {
k := strings.IndexByte(binary, '0')
if k == -1 {
return binary
}
for _, c := range binary[k+1:] {
if c == '0' {
k++
}
}
ans := []byte(binary)
for i := range ans {
ans[i] = '1'
}
ans[k] = '0'
return string(ans)
}

• function maximumBinaryString(binary: string): string {
let k = binary.indexOf('0');
if (k === -1) {
return binary;
}
k += binary.slice(k + 1).split('0').length - 1;
return '1'.repeat(k) + '0' + '1'.repeat(binary.length - k - 1);
}


• public class Solution {
public string MaximumBinaryString(string binary) {
int k = binary.IndexOf('0');
if (k == -1) {
return binary;
}
k += binary.Substring(k + 1).Count(c => c == '0');
return new string('1', k) + '0' + new string('1', binary.Length - k - 1);
}
}

• impl Solution {
pub fn maximum_binary_string(binary: String) -> String {
if let Some(k) = binary.find('0') {
let k =
k +
binary[k + 1..]
.chars()
.filter(|&c| c == '0')
.count();
return format!("{}{}{}", "1".repeat(k), "0", "1".repeat(binary.len() - k - 1));
}
binary
}
}