Skip to content

Latest commit

 

History

History
218 lines (176 loc) · 6.15 KB

README_EN.md

File metadata and controls

218 lines (176 loc) · 6.15 KB
comments difficulty edit_url rating source tags
true
Medium
1825
Biweekly Contest 42 Q3
Greedy
String

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

Solutions

Solution 1: Quick Thinking

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.

Python3

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)

Java

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

C++

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');
    }
};

Go

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

TypeScript

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

Rust

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

C#

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