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
"
- 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'
.
Related Topics:
Greedy
Solution 1. Greedy
For leading 00
, we always replace it with 10
.
For pattern 01...10
(1
s surrounded by 0
s), 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 0
s.
// 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
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);
}
}