Skip to content

1702. Maximum Binary String After Change

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

Solutions

Solution 1: Quick Thinking

Thinking

The operations replace \(00\) with \(10\) and \(10\) with \(01\). Searching every rewrite grows exponentially with the string length and will not finish under the constraints.

Operation 2 can slide any \(1\) rightward; operation 1 collapses a run of zeros into ones followed by a single \(0\). The optimal string therefore contains at most one \(0\), placed as far right as possible.

Leading ones before the first \(0\) cannot change. All later zeros can be gathered to one index: if the first \(0\) is at \(k\), add the number of zeros after it to obtain the final \(0\) position, and fill the rest with ones.

We observe that operation \(2\) can move all \(1\)s to the end of the string, and operation \(1\) can change all 0000..000 strings to 111..110.

Therefore, to get the maximum binary string, we should move all \(1\)s that are not at the beginning to the end of the string, making the string in the form of 111..11...000..00..11. Then, with the help of operation \(1\), we change the middle 000..00 to 111..10. In this way, we can finally get a binary string that contains at most one \(0\), which is the maximum binary string we are looking for.

In the code implementation, we first judge whether the string contains \(0\). If it does not, we directly return the original string. Otherwise, we find the position \(k\) of the first \(0\), add the number of \(0\)s after this position, and the position of \(0\) in the modified string is obtained. The rest of the positions are all \(1\)s.

The time complexity is \(O(n)\), and the space complexity is \(O(n)\). Where \(n\) is the length of the string.

1
2
3
4
5
6
7
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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    string maximumBinaryString(string binary) {
        int k = binary.find('0');
        if (k == binary.npos) {
            return binary;
        }
        int n = binary.size();
        for (int i = k + 1; i < n; ++i) {
            if (binary[i] == '0') {
                ++k;
            }
        }
        return string(k, '1') + '0' + string(n - k - 1, '1');
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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)
}

1
2
3
4
5
6
7
8
function maximumBinaryString(binary: string): string {
    let k = binary.indexOf('0');
    if (k === -1) {
        return binary;
    }
    k += binary.slice(k + 1).split('0').length - 1;
    return '1'.repeat(k) + '0' + '1'.repeat(binary.length - k - 1);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
impl Solution {
    pub fn maximum_binary_string(binary: String) -> String {
        if let Some(k) = binary.find('0') {
            let k = k + binary[k + 1..].chars().filter(|&c| c == '0').count();
            return format!(
                "{}{}{}",
                "1".repeat(k),
                "0",
                "1".repeat(binary.len() - k - 1)
            );
        }
        binary
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
public class Solution {
    public string MaximumBinaryString(string binary) {
        int k = binary.IndexOf('0');
        if (k == -1) {
            return binary;
        }
        k += binary.Substring(k + 1).Count(c => c == '0');
        return new string('1', k) + '0' + new string('1', binary.Length - k - 1);
    }
}

Comments