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, "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 <= 10⁵
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 (1s surrounded by 0s), 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 0s.

// 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);
    }
}

// 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;
    }
};

# 1702. Maximum Binary String After Change
# https://leetcode.com/problems/maximum-binary-string-after-change/

class Solution:
    def maximumBinaryString(self, binary: str) -> str:
        if "0" not in binary: return binary
        
        n = len(binary)
        first = binary.index('0')
        
        res = []
        for _ in range(first):
            res.append("1")
        
        zeroes = ones = 0
        for i in range(first, n):
            if binary[i] == "0":
                zeroes += 1
            else:
                ones += 1
        
        while zeroes > 1:
            res.append("1")
            zeroes -= 1
        
        res.append("0")
        
        while ones > 0:
            res.append("1")
            ones -= 1
        
        return "".join(res)
        

1702 - Maximum Binary String After Change

1702. Maximum Binary String After Change (Medium)

Solution 1. Greedy

All Problems

All Solutions