Description
You are given a binary string s of length n, where:
'1'represents an active section.'0'represents an inactive section.
You can perform at most one trade to maximize the number of active sections in s. In a trade, you:
- Convert a contiguous block of
'1's that is surrounded by'0's to all'0's. - Afterward, convert a contiguous block of
'0's that is surrounded by'1's to all'1's.
Return the maximum number of active sections in s after making the optimal trade.
Note: Treat s as if it is augmented with a '1' at both ends, forming t = '1' + s + '1'. The augmented '1's do not contribute to the final count.
Example 1:
Input: s = "01"
Output: 1
Explanation:
Because there is no block of '1's surrounded by '0's, no valid trade is possible. The maximum number of active sections is 1.
Example 2:
Input: s = "0100"
Output: 4
Explanation:
- String
"0100"→ Augmented to"101001". - Choose
"0100", convert"101001"→"100001"→"111111". - The final string without augmentation is
"1111". The maximum number of active sections is 4.
Example 3:
Input: s = "1000100"
Output: 7
Explanation:
- String
"1000100"→ Augmented to"110001001". - Choose
"000100", convert"110001001"→"110000001"→"111111111". - The final string without augmentation is
"1111111". The maximum number of active sections is 7.
Example 4:
Input: s = "01010"
Output: 4
Explanation:
- String
"01010"→ Augmented to"1010101". - Choose
"010", convert"1010101"→"1000101"→"1111101". - The final string without augmentation is
"11110". The maximum number of active sections is 4.
Constraints:
1 <= n == s.length <= 105s[i]is either'0'or'1'
Solutions
This corrected version refines the prefix/suffix zero-run technique by 1-indexing the prefixSum/suffixSum arrays and, crucially, checking s[i - 1] === '1' before combining them, so a merge is only counted when it's genuinely centered on a 1 character between two zero-runs. It returns 0 immediately if the string has no 1s, otherwise it returns the total ones count plus the best combined zero-run length found this way.
/**
* @param {string} s
* @return {number}
*/
var maxActiveSectionsAfterTrade = function(s) {
const n = s.length;
const prefixSum = Array(n + 2).fill(0);
const suffixSum = Array(n + 2).fill(0);
let ones = 0;
for (let i = 0; i < n; i++) {
if (s[i] === '0') {
if (s[i] === s[i - 1]) {
prefixSum[i + 1] = prefixSum[i] + 1;
} else {
prefixSum[i + 1] = 1;
}
} else {
prefixSum[i + 1] = prefixSum[i];
ones++;
}
const j = n - 1 - i;
if (s[j] === '0') {
if (s[j] === s[j + 1]) {
suffixSum[j + 1] = suffixSum[j + 2] + 1;
} else {
suffixSum[j + 1] = 1;
}
} else {
suffixSum[j + 1] = suffixSum[j + 2];
}
}
if (ones === 0) return 0;
let maxZeros = 0;
for (let i = 1; i <= n; i++) {
if (prefixSum[i] > 0 && suffixSum[i] > 0 && s[i - 1] === '1') {
maxZeros = Math.max(maxZeros, prefixSum[i] + suffixSum[i]);
}
}
return ones + maxZeros;
};