Welcome to Subscribe On Youtube
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;
}
};
-
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); } } ############ 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); } }
-
// 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; } };
-
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) ############ # 1702. Maximum Binary String After Change # https://leetcode.com/problems/maximum-binary-string-after-change/ class Solution: def maximumBinaryString(self, binary: str) -> str: if "0" not in binary: return binary n = len(binary) first = binary.index('0') res = [] for _ in range(first): res.append("1") zeroes = ones = 0 for i in range(first, n): if binary[i] == "0": zeroes += 1 else: ones += 1 while zeroes > 1: res.append("1") zeroes -= 1 res.append("0") while ones > 0: res.append("1") ones -= 1 return "".join(res)
-
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) }