1702. Maximum Binary String After Change LeetCode Solution

In this guide, you will get 1702. Maximum Binary String After Change LeetCode Solution with the best time and space complexity. The solution to Maximum Binary String After Change problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Maximum Binary String After Change solution in C++
Maximum Binary String After Change solution in Java
Maximum Binary String After Change solution in Python
Additional Resources

1702. Maximum Binary String After Change LeetCode Solution image

Problem Statement of Maximum Binary String After Change

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'.

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

1702. Maximum Binary String After Change LeetCode Solution in C++

class Solution {
 public:
  string maximumBinaryString(string binary) {
    //     e.g. binary = "100110"
    // Do Operation 2 -> "100011"
    // Do Operation 1 -> "111011"
    // So, the index of the only '0' is prefixOnes + zeros - 1.
    const int zeros = ranges::count(binary, '0');
    const int prefixOnes = binary.find('0');

    // Make the entire string as 1s.
    binary.assign(binary.length(), '1');

    // Make the only '0' if necessary.
    if (prefixOnes != string::npos)
      binary[prefixOnes + zeros - 1] = '0';
    return binary;
  }
};
/* code provided by PROGIEZ */

1702. Maximum Binary String After Change LeetCode Solution in Java

class Solution {
  public String maximumBinaryString(String binary) {
    //     e.g. binary = "100110"
    // Do Operation 2 -> "100011"
    // Do Operation 1 -> "111011"
    // So, the index of the only '0' is prefixOnes + zeros - 1.
    final int zeros = (int) binary.chars().filter(c -> c == '0').count();
    final int prefixOnes = binary.indexOf('0');

    // Make the entire String as 1s.
    StringBuilder sb = new StringBuilder("1".repeat(binary.length()));

    // Make the only '0' if necessary.
    if (prefixOnes != -1)
      sb.setCharAt(prefixOnes + zeros - 1, '0');
    return sb.toString();
  }
}
// code provided by PROGIEZ

1702. Maximum Binary String After Change LeetCode Solution in Python

class Solution:
  def maximumBinaryString(self, binary: str) -> str:
    #     e.g. binary = '100110'
    # Do Operation 2 -> '100011'
    # Do Operation 1 -> '111011'
    # So, the index of the only '0' is prefixOnes + zeros - 1.
    zeros = binary.count('0')
    prefixOnes = binary.find('0')

    # Make the entire string as 1s.
    ans = ['1'] * len(binary)

    # Make the only '0' if necessary.
    if prefixOnes != -1:
      ans[prefixOnes + zeros - 1] = '0'
    return ''.join(ans)
 # code by PROGIEZ