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, forming t = '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

1
2
3
4
5

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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^5
  • 1 <= queries.length <= 10^5
  • s[i] is either '0' or '1'.
  • queries[i] = [li, ri]
  • 0 <= li <= ri < n

Examples

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

  1. For each query [l, r], extract s[l..r] and augment as t = '1' + s[l..r] + '1'.
  2. Find all blocks of ‘1’s surrounded by ‘0’s and all blocks of ‘0’s surrounded by ‘1’s in t.
  3. 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.
  4. If no valid trade, return the count of ‘1’s in the substring.
  5. Repeat for all queries and return the results.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

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), where q is the number of queries and m is 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.