Difficulty: 🔴 Hard
Topics: Array, String, Binary Search, Segment Tree

Solution

Problem Understanding

The problem presents a binary string s where each character represents an active ('1') or inactive ('0') section. For each query, which specifies a substring of s, we are asked to determine the maximum number of active sections after performing at most one trade operation. A trade consists of converting a contiguous block of '1's that is surrounded by '0's into '0's, followed by converting a contiguous block of '0's surrounded by '1's into '1's. Each query substring is augmented with a '1' at both ends, which are only used to determine if a block is surrounded and do not count toward the final active section count.

In simpler terms, for each query, we are allowed one swap of a 1-block to a 0-block and a 0-block to a 1-block within the substring to maximize '1's. The challenge is to compute this efficiently, given that both s and queries can be as large as 10^5. Edge cases include substrings that already consist of all '1's or '0's, very small substrings, or substrings where no trade is possible because there is no '1' or '0' block fully surrounded by the opposite character. For a query [l, r], we do not work directly on the whole string s. Instead, we consider only the substring

$$u = s[l \dots r].$$

The problem then augments this substring with a virtual '1' on both sides:

$$t = 1 + u + 1.$$

The virtual boundary characters are used only to determine which blocks are considered "surrounded", they do not contribute to the final active count.

A trade consists of two operations performed in order.

First, choose a contiguous block of '1's that is surrounded by '0's and turn the entire block into '0's.

Second, choose a contiguous block of '0's that is surrounded by '1's and turn the entire block into '1's.

The goal is to maximize the number of active sections, that is, the number of '1's in the original substring.

The constraints are

$$n \le 10^5,\qquad |queries| \le 10^5.$$

Therefore a solution that processes each query independently in linear time is far too slow. We need approximately logarithmic query time.

Key Structural Observation

Suppose in the augmented string we have

$$0^a,1^b,0^c$$

where the middle 1-run is surrounded by the two adjacent 0-runs.

If we choose that 1-run for the first part of the trade, it becomes

$$0^{a+b+c}.$$

This newly merged zero block is surrounded by 1s, so it can be selected in the second part of the trade and converted to

$$1^{a+b+c}.$$

The net gain in the number of active sections is

$$(a+b+c)-b=a+c.$$

Therefore the only thing that matters is:

find a pattern 0+ 1+ 0+
maximize

$$(\text{length of first }0\text{-run}) + (\text{length of second }0\text{-run}).$$

If no such pattern exists, no valid trade exists and the answer is simply the number of existing '1's.

Approaches

Brute Force

The naive approach would be, for each query, to iterate over all possible '1' blocks surrounded by '0's, simulate the trade by flipping each eligible '1' block to '0' and each '0' block to '1', then count the number of '1's after the operation. This ensures correctness because we explicitly check all possible trades.

The problem with this approach is its time complexity. For each query, identifying all blocks and simulating flips would take O(length of substring), and there could be up to 10^5 queries. In the worst case, this results in O(n * q) time, which is up to 10^10 operations - clearly infeasible.

Optimal Approach

The key insight is that within each query, to maximize '1's, we do not need to try all combinations. By analyzing the augmented substring, we can:

Count total '1's initially.
Identify the longest '0' block fully surrounded by '1's (because this is the block we would convert to '1's).
Identify any '1' blocks that can be converted to '0's, but for maximization, we generally only want to convert the smallest '1' block if necessary. The optimal trade often involves converting all surrounding 0s into 1s without removing too many existing 1s.

Since each query is independent, we can process each substring separately, scanning it linearly and maintaining counts of contiguous blocks. This gives an O(substring length) solution per query, which is acceptable given the constraints if the substring lengths are small on average, but for worst-case long substrings, we can precompute prefix sums and block boundaries to quickly compute maximum gain.

This reduces the brute-force simulation to an O(n) pass per query using prefix sums for '1's and tracking max-length '0' blocks surrounded by '1's.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * q)	O(n)	Explicitly simulates every trade for every query
Optimal	O(n + q)	O(n)	Uses prefix sums and block tracking to compute max gain per query

Algorithm Walkthrough

Precompute Prefix Sum of '1's: Create an array prefix_ones where prefix_ones[i] stores the total number of '1's in s[0...i-1]. This allows O(1) calculation of '1's in any substring.
Process Each Query Independently: For a query [l, r], extract the substring s[l...r] and augment it as '1' + s[l...r] + '1'.
Identify Blocks: Scan the augmented substring to track contiguous blocks of '0's surrounded by '1's. Record the length of the longest '0' block that can be converted to '1'.
Calculate Maximum Active Sections: Compute the total number of '1's in the original substring using the prefix sum. The maximum number of '1's after the optimal trade is the total initial '1's plus the length of the longest '0' block surrounded by '1's.
Return Answer: Collect results for each query into an array.

Why it works: By augmenting the substring with '1's at both ends, we ensure every '0' block eligible for conversion is fully surrounded by '1's. Counting only the longest '0' block ensures we maximize '1's with a single trade. This invariant guarantees correctness. For each query, explicitly build the augmented substring, enumerate every valid surrounded 1-block, perform the trade, and compute the resulting number of active sections.

This is correct because it directly simulates every legal operation.

However, a query can have length $O(n)$, and there are $10^5$ queries. Even $O(n)$ work per query is already too expensive.

Optimal Approach

The previous observation reduces the problem to:

count the number of '1's in the query range,
compute the maximum value represented by a pattern

$$0^+1^+0^+$$

where only the zeros contribute to the score.

This becomes a range-query problem.

We build a segment tree whose node stores a max-plus transition matrix for a small automaton recognizing the pattern 0+1+0+.

Matrix multiplication combines adjacent segments, allowing a query range to be answered in $O(\log n)$.

Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	$O(n)$ per query	$O(1)$	Enumerates all possible trades
Optimal	$O(\log n)$ per query	$O(n)$	Segment tree with max-plus matrices

Algorithm Walkthrough

Automaton States

We use five states.

State 0: not started.
State 1: currently inside the first zero block.
State 2: currently inside the middle one block.
State 3: currently inside the second zero block.
State 4: finished.

The score is the total number of zeros used in states 1 and 3.

Per-Character Transition Matrix

For every character we create a $5\times5$ max-plus matrix.

For a '0':

state 0 may start the first zero block,
state 1 may continue the first zero block,
state 2 may start the second zero block,
state 3 may continue the second zero block.

Each zero contributes +1 whenever it belongs to one of the two zero blocks.

For a '1':

state 1 may transition to state 2,
state 2 may continue.

States 0 and 4 allow arbitrary skipping.

Segment Tree

Each leaf stores the matrix corresponding to one character.

For two adjacent segments $A$ and $B$, their combined matrix is

$$A \otimes B$$

using max-plus matrix multiplication.

This represents processing the left segment followed by the right segment.

Query

For a range [l,r]:

Obtain the combined matrix for that interval.
Start with DP value 0 in state 0 and $-\infty$ elsewhere.
Apply the matrix.
The maximum gain is the best value reaching states 3 or 4.
Compute the number of existing ones using a prefix-sum array.
If no valid pattern exists, gain is 0.
Return

$$\text{ones}+\text{gain}.$$

Why it works

The automaton accepts exactly strings containing a contiguous pattern

$$0^+1^+0^+.$$

The score accumulated by the automaton equals the total length of the two zero runs. Earlier we proved that this quantity is exactly the net increase produced by the optimal trade. Therefore the maximum score returned by the automaton equals the maximum attainable gain. Adding that gain to the original number of active sections gives the optimal answer.

Python Solution

from typing import List

class Solution:
    def maxActiveSectionsAfterTrade(self, s: str, queries: List[List[int]]) -> List[int]:
        n = len(s)
        # Prefix sum of '1's for quick counting
        prefix_ones = [0] * (n + 1)
        for i in range(n):
            prefix_ones[i+1] = prefix_ones[i] + (s[i] == '1')
        
        answer = []
        for l, r in queries:
            substring = '1' + s[l:r+1] + '1'
            max_zero_block = 0
            current_zero_len = 0
            for char in substring:
                if char == '0':
                    current_zero_len += 1
                else:
                    if current_zero_len > 0:
                        max_zero_block = max(max_zero_block, current_zero_len)
                        current_zero_len = 0
            total_ones = prefix_ones[r+1] - prefix_ones[l]
            answer.append(total_ones + max_zero_block)
        return answer

Explanation: We first precompute prefix_ones to allow O(1) retrieval of total '1's in any substring. For each query, we augment the substring and scan it to identify the longest '0' block surrounded by '1's. The sum of initial '1's and the longest '0' block gives the maximum number of active sections. NEG = -10**18 SIZE = 5

def mat_mul(a, b): res = [[NEG] * SIZE for _ in range(SIZE)] for i in range(SIZE): for k in range(SIZE): if a[i][k] == NEG: continue aik = a[i][k] for j in range(SIZE): if b[k][j] == NEG: continue res[i][j] = max(res[i][j], aik + b[k][j]) return res

def char_matrix(ch: str): m = [[NEG] * SIZE for _ in range(SIZE)]

m[0][0] = 0
m[4][4] = 0

if ch == '0':
    m[0][1] = 1
    m[1][1] = 1
    m[2][3] = 1
    m[3][3] = 1

    m[3][4] = 0
else:
    m[1][2] = 0
    m[2][2] = 0

    m[3][4] = 0

return m

class Solution: def maxActiveSectionsAfterTrade( self, s: str, queries: List[List[int]] ) -> List[int]:

    n = len(s)

    pref = [0] * (n + 1)
    for i, ch in enumerate(s):
        pref[i + 1] = pref[i] + (ch == '1')

    size = 1
    while size < n:
        size <<= 1

    ident = [[NEG] * SIZE for _ in range(SIZE)]
    for i in range(SIZE):
        ident[i][i] = 0

    seg = [ident for _ in range(2 * size)]

    for i, ch in enumerate(s):
        seg[size + i] = char_matrix(ch)

    for i in range(size - 1, 0, -1):
        seg[i] = mat_mul(seg[i << 1], seg[i << 1 | 1])

    def query(l, r):
        left = ident
        right = ident

        l += size
        r += size + 1

        while l < r:
            if l & 1:
                left = mat_mul(left, seg[l])
                l += 1
            if r & 1:
                r -= 1
                right = mat_mul(seg[r], right)
            l >>= 1
            r >>= 1

        return mat_mul(left, right)

    ans = []

    for l, r in queries:
        ones = pref[r + 1] - pref[l]

        mat = query(l, r)

        gain = max(mat[0][3], mat[0][4])
        if gain < 0:
            gain = 0

        ans.append(ones + gain)

    return ans


### Implementation Discussion

The prefix-sum array allows the number of active sections already present in a query interval to be obtained in constant time.

Each segment-tree node stores the max-plus transition matrix of its interval. Combining nodes corresponds exactly to concatenating substrings.

A query retrieves the matrix of the requested interval. The best automaton score reachable from the initial state gives the maximum gain obtainable from a trade. That gain is added to the existing number of active sections.

## Go Solution

```go
func maxActiveSectionsAfterTrade(s string, queries [][]int) []int {
    n := len(s)
    prefixOnes := make([]int, n+1)
    for i := 0; i < n; i++ {
        prefixOnes[i+1] = prefixOnes[i]
        if s[i] == '1' {
            prefixOnes[i+1]++
        }
    }
    
    answer := make([]int, len(queries))
    for idx, q := range queries {
        l, r := q[0], q[1]
        substring := "1" + s[l:r+1] + "1"
        maxZero := 0
        currentZero := 0
        for i := 0; i < len(substring); i++ {
            if substring[i] == '0' {
                currentZero++
            } else {
                if currentZero > 0 {
                    if currentZero > maxZero {
                        maxZero = currentZero
                    }
                    currentZero = 0
                }
            }
        }
        totalOnes := prefixOnes[r+1] - prefixOnes[l]
        answer[idx] = totalOnes + maxZero
    }
    return answer
}

Go-specific notes: We use slices for prefix sums. Strings are indexed as bytes, so substring[i] == '0' works directly. No explicit dynamic resizing is required since make initializes slices with fixed length.

Worked Examples

Example: s = "0100", queries = [[0,3],[0,2],[1,3],[2,3]]

For query [0,3]:

Substring "0100" → augmented "101001"
Max '0' block surrounded by '1's = 4 ("0100")
Total initial '1's = 1 ('1' at index 1)
Maximum active sections = 1 + 3 = 4

Other queries follow the same logic, scanning the augmented substring to find the longest '0' block and adding it to initial '1' count. package main

const NEG int64 = -1 << 60 const SIZE = 5

type Matrix [SIZE][SIZE]int64

func identity() Matrix { var m Matrix for i := 0; i < SIZE; i++ { for j := 0; j < SIZE; j++ { m[i][j] = NEG } m[i][i] = 0 } return m }

func mul(a, b Matrix) Matrix { var res Matrix

for i := 0; i < SIZE; i++ {
	for j := 0; j < SIZE; j++ {
		res[i][j] = NEG
	}
}

for i := 0; i < SIZE; i++ {
	for k := 0; k < SIZE; k++ {
		if a[i][k] == NEG {
			continue
		}
		for j := 0; j < SIZE; j++ {
			if b[k][j] == NEG {
				continue
			}
			val := a[i][k] + b[k][j]
			if val > res[i][j] {
				res[i][j] = val
			}
		}
	}
}

return res

}

func charMatrix(ch byte) Matrix { m := identity()

if ch == '0' {
	m[0][1] = 1
	m[1][1] = 1
	m[2][3] = 1
	m[3][3] = 1
	m[3][4] = 0
} else {
	m[1][2] = 0
	m[2][2] = 0
	m[3][4] = 0
}

return m

}

func maxActiveSectionsAfterTrade(s string, queries [][]int) []int { n := len(s)

pref := make([]int, n+1)
for i := 0; i < n; i++ {
	pref[i+1] = pref[i]
	if s[i] == '1' {
		pref[i+1]++
	}
}

size := 1
for size < n {
	size <<= 1
}

id := identity()

seg := make([]Matrix, 2*size)

for i := range seg {
	seg[i] = id
}

for i := 0; i < n; i++ {
	seg[size+i] = charMatrix(s[i])
}

for i := size - 1; i > 0; i-- {
	seg[i] = mul(seg[i<<1], seg[i<<1|1])
}

query := func(l, r int) Matrix {
	left := id
	right := id

	l += size
	r += size + 1

	for l < r {
		if l&1 == 1 {
			left = mul(left, seg[l])
			l++
		}
		if r&1 == 1 {
			r--
			right = mul(seg[r], right)
		}
		l >>= 1
		r >>= 1
	}

	return mul(left, right)
}

ans := make([]int, len(queries))

for idx, q := range queries {
	l, r := q[0], q[1]

	ones := pref[r+1] - pref[l]

	mat := query(l, r)

	gain := mat[0][3]
	if mat[0][4] > gain {
		gain = mat[0][4]
	}
	if gain < 0 {
		gain = 0
	}

	ans[idx] = ones + int(gain)
}

return ans

}


### Go-Specific Notes

The implementation uses `int64` for matrix values to avoid overflow concerns and to provide a convenient negative-infinity sentinel.

Matrices are stored as fixed-size arrays, which avoids heap allocations during multiplication and improves performance.

## Worked Examples

### Example 1

Input:

s = "01" query = [0,1]


The substring contains one active section.

There is no `0+1+0+` pattern.

| Value | Result |
| --- | --- |
| Existing ones | 1 |
| Gain | 0 |
| Answer | 1 |

### Example 2, Query [0,3]

0100


The pattern

0 1 00


exists.

| Left zero run | Middle one run | Right zero run |
| --- | --- | --- |
| 1 | 1 | 2 |

Gain:

$$1+2=3$$

Existing ones:

$$1$$

Answer:

$$1+3=4$$

### Example 3, Query [0,6]

1000100


Pattern:

000 1 00


Gain:

$$3+2=5$$

Existing ones:

$$2$$

Answer:

$$2+5=7$$

### Example 4, Query [1,3]

101


There is no valid `0+1+0+` structure.

| Value | Result |
| --- | --- |
| Existing ones | 2 |
| Gain | 0 |
| Answer | 2 |

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(n + total query substring length) | Prefix sum is O(n), each query is O(length of substring) |
| Space | O(n) | Prefix sum array, plus output array |

Because each query is independent, the algorithm scales well even for the maximum constraints, assuming typical substring lengths are reasonable.
| Time | $O((n+q)\log n)$ | Segment-tree range queries |
| Space | $O(n)$ | Segment tree and prefix sums |

Each matrix multiplication operates on a fixed $5 \times 5$ matrix, therefore its cost is constant. The only non-constant factor comes from the segment-tree height.

## Test Cases

sln = Solution()

Provided examples

assert sln.maxActiveSectionsAfterTrade("01", [[0,1]]) == [1] assert sln.maxActiveSectionsAfterTrade("0100", [[0,3],[0,2],[1,3],[2

sol = Solution()

assert sol.maxActiveSectionsAfterTrade(
    "01",
    [[0, 1]]
) == [1]  # sample 1

assert sol.maxActiveSectionsAfterTrade(
    "0100",
    [[0, 3], [0, 2], [1, 3], [2, 3]]
) == [4, 3, 1, 1]  # sample 2

assert sol.maxActiveSectionsAfterTrade(
    "1000100",
    [[1, 5], [0, 6], [0, 4]]
) == [6, 7, 2]  # sample 3

assert sol.maxActiveSectionsAfterTrade(
    "01010",
    [[0, 3], [1, 4], [1, 3]]
) == [4, 4, 2]  # sample 4

assert sol.maxActiveSectionsAfterTrade(
    "11111",
    [[0, 4]]
) == [5]  # all ones

assert sol.maxActiveSectionsAfterTrade(
    "00000",
    [[0, 4]]
) == [0]  # all zeros

assert sol.maxActiveSectionsAfterTrade(
    "010",
    [[0, 2]]
) == [3]  # smallest valid trade

assert sol.maxActiveSectionsAfterTrade(
    "001100",
    [[0, 5]]
) == [6]  # full conversion possible

assert sol.maxActiveSectionsAfterTrade(
    "10101",
    [[0, 4]]
) == [4]  # multiple small runs

assert sol.maxActiveSectionsAfterTrade(
    "1",
    [[0, 0]]
) == [1]  # minimum length, one

assert sol.maxActiveSectionsAfterTrade(
    "0",
    [[0, 0]]
) == [0]  # minimum length, zero

Test Summary

Test	Why
`"01"`	No valid trade
`"0100"`	Sample containing beneficial trade
`"1000100"`	Large gain from merging runs
`"01010"`	Multiple competing patterns
All ones	No surrounded one block
All zeros	No middle one block
`"010"`	Smallest nontrivial valid trade
`"001100"`	Entire interval becomes active
`"10101"`	Several short runs
Single character one	Minimum size
Single character zero	Minimum size

Edge Cases

No Valid Internal One Block

A substring may contain active sections but no 1-run surrounded by zeros. Examples include "11111" and "101".

A careless implementation might incorrectly force a trade. The automaton naturally rejects such intervals, producing a negative score, which is converted to gain zero.

All Zeros

If a query contains only zeros, there is no middle 1-run at all. Therefore no trade is legal.

The implementation correctly reports gain zero and returns the existing number of active sections, namely zero.

Multiple Candidate Trades

A substring such as "0100010010" contains several possible 0+1+0+ structures.

Choosing the longest middle 1-run is not necessarily optimal. The true objective is maximizing the sum of the two surrounding zero-run lengths.

The automaton evaluates all valid possibilities simultaneously and returns the maximum score, guaranteeing the optimal trade is chosen.

LeetCode 3501 - Maximize Active Section with Trade II

Solution

Problem Understanding

Key Structural Observation

Approaches

Brute Force

Optimal Approach

Algorithm Walkthrough

Optimal Approach

Comparison

Algorithm Walkthrough

Automaton States

Per-Character Transition Matrix

Segment Tree

Query

Why it works

Python Solution

Worked Examples

Provided examples

Test Summary

Edge Cases

No Valid Internal One Block

All Zeros

Multiple Candidate Trades