Maximize Active Section with Trade II
HardUpdated: Aug 2, 2025
Practice on:
Problem
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.
Examples
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 <= 10^51 <= queries.length <= 10^5s[i]is either'0'or'1'.queries[i] = [li, ri]0 <= li <= ri < n
Solution
Method 1 – Block Preprocessing and Greedy Simulation per Query
Intuition
For each query substring, we want to maximize the number of '1's after at most one trade (remove a block of '1's surrounded by '0's, then flip a block of '0's surrounded by '1's). We preprocess the substring for all such blocks and simulate all possible trades for each query.
Approach
- For each query
[l, r], extracts[l..r]and augment ast = '1' + s[l..r] + '1'. - Find all blocks of '1's surrounded by '0's and all blocks of '0's surrounded by '1's in
t. - For each possible pair (remove a '1' block, flip a '0' block), simulate the trade:
- Remove the '1' block (set to '0'), then flip the '0' block (set to '1').
- Count the number of '1's in the resulting string (excluding the augmented ends).
- Track the maximum.
- If no valid trade, return the count of '1's in the substring.
- Repeat for all queries and return the results.
Code
Python
class Solution:
def maximizeActiveSections(self, s: str, queries: list[list[int]]) -> list[int]:
res = []
for l, r in queries:
sub = s[l:r+1]
t = '1' + sub + '1'
n = len(t)
ones, zeros = [], []
i = 0
while i < n:
if t[i] == '1' and t[i-1] == '0':
j = i
while j < n and t[j] == '1':
j += 1
if t[j] == '0':
ones.append((i, j-1))
i = j
elif t[i] == '0' and t[i-1] == '1':
j = i
while j < n and t[j] == '0':
j += 1
if t[j] == '1':
zeros.append((i, j-1))
i = j
else:
i += 1
ans = sub.count('1')
for o in ones:
for z in zeros:
tmp = list(t)
for k in range(o[0], o[1]+1):
tmp[k] = '0'
for k in range(z[0], z[1]+1):
tmp[k] = '1'
cnt = sum(1 for k in range(1, n-1) if tmp[k] == '1')
ans = max(ans, cnt)
res.append(ans)
return res
Complexity
- ⏰ Time complexity:
O(q * m^2), whereqis the number of queries andmis the length of the substring in each query, as we may try all pairs of blocks per query. - 🧺 Space complexity:
O(m), for storing the augmented substring and temporary arrays per query.