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
"
- For example,
- Operation 2: If the number contains the substring
"10"
, you can replace it with"01"
.- For example,
"00010" -> "00001"
- For example,
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.
1 2 3 4 5 6 7 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 |
|