1702

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

  <ul>
  	<li>For example, <code>"<u>00</u>010" -&gt; "<u>10</u>010</code>"</li>
  </ul>
  </li>
  <li>Operation 2: If the number contains the substring <code>"10"</code>, you can replace it with <code>"01"</code>.
  <ul>
  	<li>For example, <code>"000<u>10</u>" -&gt; "000<u>01</u>"</code></li>
  </ul>
  </li>
  

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/
// Author: github.com/lzl124631x
// 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;
    }
};