Maximum Binary String After Change - Leetcode Solution

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

Return the maximum binary string you can obtain after any number of operations.

Note: Binary string x is greater than binary string y if x's decimal representation is greater than y's decimal representation.

Example:

Input: binary = "000110" Output: "111011" Explanation: A valid transformation sequence can be: "000110" -> "000101" "000101" -> "100101" "100101" -> "110101" "110101" -> "110011" "110011" -> "111011"

Solution:

We can apply the following approach to solve this problem.

1. Count the number of zeros and ones in the input binary string.
2. If there are no zeros, return the input binary string as it is.
3. If there are no ones, return the input binary string as it is.
4. If there are some ones and zeros, put all ones at the beginning of the output string and put the remaining zeros at the end of the output string.
5. If there are more zeros than ones, replace all "00" substrings with "10" substrings until there are no more "00" substrings.
6. If there are more ones than zeros, replace all "10" substrings with "01" substrings until there are no more "10" substrings.

Let's take the example "000110" and apply the above approach.

1. Count the number of zeros and ones in the input string. There are 3 zeros and 3 ones.
2. There are both zeros and ones in the input string.
3. Put all ones at the beginning and zeros at the end of the output string. The output string becomes "111000".
4. As the number of zeros is greater than the number of ones, replace all "00" substrings with "10" substrings until there are no more "00" substrings. The output string becomes "111011".

Hence the maximum binary string after change is "111011".

Code implementation:

Here is the Python code implementation for this problem.

class Solution:
    def maximumBinaryString(self, binary: str) -> str:
        zeros = binary.count('0')
        ones = binary.count('1')
        if zeros == 0:
            return binary
        if ones == 0:
            return binary
        result = '1' * ones + '0' * (zeros - 1)
        while '00' in result:
            index = result.index('00')
            result = result[:index] + '10' + result[index + 2:]
        return result

Time Complexity: O(n^2), where n is the length of the input string binary.

Space Complexity: O(n), where n is the length of the input string binary.

1