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.
Additionally, you are given a 2D array queries, where queries[i] = [li, ri] represents a substring s[li...ri].
For each query, determine the maximum possible number of active sections in s after making the optimal trade on the substring s[li...ri].
Return an array answer, where answer[i] is the result for queries[i].
Note
- For each query, treat
s[li...ri]as if it is augmented with a'1'at both ends, formingt = '1' + s[li...ri] + '1'. The augmented'1's do not contribute to the final count. - The queries are independent of each other.
Example 1:
Input: s = "01", queries = [[0,1]]
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", queries = [[0,3],[0,2],[1,3],[2,3]]
Output: [4,3,1,1]
Explanation:
-
Query
[0, 3]→ Substring"0100"→ Augmented to"101001"
Choose"0100", convert"0100"→"0000"→"1111".
The final string without augmentation is"1111". The maximum number of active sections is 4. -
Query
[0, 2]→ Substring"010"→ Augmented to"10101"
Choose"010", convert"010"→"000"→"111".
The final string without augmentation is"1110". The maximum number of active sections is 3. -
Query
[1, 3]→ Substring"100"→ Augmented to"11001"
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. -
Query
[2, 3]→ Substring"00"→ Augmented to"1001"
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 3:
Input: s = "1000100", queries = [[1,5],[0,6],[0,4]]
Output: [6,7,2]
Explanation:
-
Query
[1, 5]→ Substring"00010"→ Augmented to"1000101"
Choose"00010", convert"00010"→"00000"→"11111".
The final string without augmentation is"1111110". The maximum number of active sections is 6. -
Query
[0, 6]→ Substring"1000100"→ Augmented to"110001001"
Choose"000100", convert"000100"→"000000"→"111111".
The final string without augmentation is"1111111". The maximum number of active sections is 7. -
Query
[0, 4]→ Substring"10001"→ Augmented to"1100011"
Because there is no block of'1's surrounded by'0's, no valid trade is possible. The maximum number of active sections is 2.
Example 4:
Input: s = "01010", queries = [[0,3],[1,4],[1,3]]
Output: [4,4,2]
Explanation:
-
Query
[0, 3]→ Substring"0101"→ Augmented to"101011"
Choose"010", convert"010"→"000"→"111".
The final string without augmentation is"11110". The maximum number of active sections is 4. -
Query
[1, 4]→ Substring"1010"→ Augmented to"110101"
Choose"010", convert"010"→"000"→"111".
The final string without augmentation is"01111". The maximum number of active sections is 4. -
Query
[1, 3]→ Substring"101"→ Augmented to"11011"
Because there is no block of'1's surrounded by'0's, no valid trade is possible. The maximum number of active sections is 2.
Constraints:
1 <= n == s.length <= 1051 <= queries.length <= 105s[i]is either'0'or'1'.queries[i] = [li, ri]0 <= li <= ri < n
Solutions
Crazy difficulty, didn't even attempt.
class SparseTable {
constructor(data) {
this.st = [[...data]];
let i = 1,
N = this.st[0].length;
while (2 * i <= N + 1) {
const pre = this.st[this.st.length - 1];
const cur = [];
for (let j = 0; j < N - 2 * i + 1; j++) {
cur.push(Math.max(pre[j], pre[j + i]));
}
this.st.push(cur);
i <<= 1;
}
}
query(begin, end) {
if (begin > end) {
return 0;
}
const len = end - begin + 1;
const lg = Math.floor(Math.log2(len));
return Math.max(this.st[lg][begin], this.st[lg][end - (1 << lg) + 1]);
}
}
function lowerBound(list, target) {
let left = 0,
right = list.length;
while (left < right) {
const mid = left + ((right - left) >> 1);
if (list[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
function upperBound(list, target) {
let left = 0,
right = list.length;
while (left < right) {
const mid = left + ((right - left) >> 1);
if (list[mid] <= target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
var maxActiveSectionsAfterTrade = function (s, queries) {
const n = s.length;
let cnt1 = 0;
for (const c of s) {
if (c === "1") {
cnt1++;
}
}
const zeroBlocks = [];
const blockLeft = [];
const blockRight = [];
let i = 0;
while (i < n) {
const st = i;
while (i < n && s[i] === s[st]) {
i += 1;
}
if (s[st] === "0") {
zeroBlocks.push(i - st);
blockLeft.push(st);
blockRight.push(i - 1);
}
}
const m = zeroBlocks.length;
if (m < 2) {
// continuous 0 blocks less than 2 segments, return the answer directly
return new Array(queries.length).fill(cnt1);
}
const tmpSum = [];
for (let k = 0; k < m - 1; k++) {
tmpSum.push(zeroBlocks[k] + zeroBlocks[k + 1]);
}
const st = new SparseTable(tmpSum);
const ans = [];
for (const q of queries) {
const l = q[0],
r = q[1];
const idx = lowerBound(blockRight, l);
const jdx = upperBound(blockLeft, r) - 1;
// at most 1 continuous block of 0s within the substring
if (idx > m - 1 || jdx < 0 || idx >= jdx) {
ans.push(cnt1);
continue;
}
const firstLen = blockRight[idx] - Math.max(blockLeft[idx], l) + 1; // actual length of the first consecutive block of 0s in the substring
const lastLen = Math.min(blockRight[jdx], r) - blockLeft[jdx] + 1; // actual length of the last consecutive block of 0s in the substring
// exactly 2 consecutive 0 blocks within the substring
if (idx + 1 === jdx) {
const bestGain = firstLen + lastLen;
ans.push(cnt1 + bestGain);
continue;
}
const val1 = firstLen + zeroBlocks[idx + 1];
const val2 = zeroBlocks[jdx - 1] + lastLen;
const val3 = st.query(idx + 1, jdx - 2);
const bestGain = Math.max(val1, val2, val3);
ans.push(cnt1 + bestGain);
}
return ans;
};