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".
    • For example, "_00_ 010" -> "_10_ 010"
  • Operation 2: If the number contains the substring "10", you can replace it with "01".
    • For example, "000 _10_ " -> "000 _01_ "

Return themaximum 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.

Examples

Example 1

1
2
3
4
5
6
7
8

Input: binary = "000110"
Output: "111011"
Explanation: A valid transformation sequence can be:
"0001 _10_ " -> "0001 _01_ " 
"_00_ 0101" -> "_10_ 0101" 
"1 _00_ 101" -> "1 _10_ 101" 
"110 _10_ 1" -> "110 _01_ 1" 
"11 _00_ 11" -> "11 _10_ 11"

Example 2

1
2
3

Input: binary = "01"
Output: "01"
Explanation:  "01" cannot be transformed any further.

Constraints

  • 1 <= binary.length <= 10^5
  • binary consist of '0' and '1'.

Solution

Method 1 – Greedy (Count Zeros and Place One Zero)

Intuition

The operations allow us to move all zeros to the right and then convert all but one zero to ones. The only zero left will be at the leftmost possible position after the first one. This is because every “00” can be turned into “10” and every “10” into “01”, so all zeros can be pushed together and then converted except one.

Approach

  1. Count the number of zeros in the string.
  2. If there are zero or one zeros, the string is already maximal.
  3. Otherwise, find the first zero’s index.
  4. The answer is all ones except for a single zero at position first_zero + zeros - 1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    string maximumBinaryString(string binary) {
        int n = binary.size(), zeros = 0, first = -1;
        for (int i = 0; i < n; ++i) {
            if (binary[i] == '0') {
                zeros++;
                if (first == -1) first = i;
            }
        }
        if (zeros <= 1) return binary;
        string ans(n, '1');
        ans[first + zeros - 1] = '0';
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

func maximumBinaryString(binary string) string {
    n := len(binary)
    zeros, first := 0, -1
    for i := 0; i < n; i++ {
        if binary[i] == '0' {
            zeros++
            if first == -1 {
                first = i
            }
        }
    }
    if zeros <= 1 {
        return binary
    }
    ans := make([]byte, n)
    for i := range ans {
        ans[i] = '1'
    }
    ans[first+zeros-1] = '0'
    return string(ans)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public String maximumBinaryString(String binary) {
        int n = binary.length(), zeros = 0, first = -1;
        for (int i = 0; i < n; ++i) {
            if (binary.charAt(i) == '0') {
                zeros++;
                if (first == -1) first = i;
            }
        }
        if (zeros <= 1) return binary;
        char[] ans = new char[n];
        Arrays.fill(ans, '1');
        ans[first + zeros - 1] = '0';
        return new String(ans);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    fun maximumBinaryString(binary: String): String {
        val n = binary.length
        var zeros = 0
        var first = -1
        for (i in binary.indices) {
            if (binary[i] == '0') {
                zeros++
                if (first == -1) first = i
            }
        }
        if (zeros <= 1) return binary
        val ans = CharArray(n) { '1' }
        ans[first + zeros - 1] = '0'
        return String(ans)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def maximumBinaryString(self, binary: str) -> str:
        n = len(binary)
        zeros = binary.count('0')
        if zeros <= 1:
            return binary
        first = binary.find('0')
        ans = ['1'] * n
        ans[first + zeros - 1] = '0'
        return ''.join(ans)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

impl Solution {
    pub fn maximum_binary_string(binary: String) -> String {
        let n = binary.len();
        let bytes = binary.as_bytes();
        let mut zeros = 0;
        let mut first = None;
        for (i, &b) in bytes.iter().enumerate() {
            if b == b'0' {
                zeros += 1;
                if first.is_none() {
                    first = Some(i);
                }
            }
        }
        if zeros <= 1 {
            return binary;
        }
        let mut ans = vec![b'1'; n];
        ans[first.unwrap() + zeros - 1] = b'0';
        String::from_utf8(ans).unwrap()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    maximumBinaryString(binary: string): string {
        const n = binary.length;
        let zeros = 0, first = -1;
        for (let i = 0; i < n; ++i) {
            if (binary[i] === '0') {
                zeros++;
                if (first === -1) first = i;
            }
        }
        if (zeros <= 1) return binary;
        const ans = Array(n).fill('1');
        ans[first + zeros - 1] = '0';
        return ans.join('');
    }
}

Complexity

  • ⏰ Time complexity: O(n), since we process each character once.
  • 🧺 Space complexity: O(n), for the output string.