Welcome to Subscribe On Youtube

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 <= 105
• 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
• C++
• Python
• Go

• 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);
      }
  }
  
  ############
  
  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);
      }
  }
  

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

• 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)
  
  ############
  
  # 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)
          
  

• 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)
  }
  

All Problems

All Solutions