Skip to content

3501. Maximize Active Section with Trade II

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, 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:

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

Solutions

Solution 1: Sparse Table

Thinking

Scanning every '0' run inside a query is \(\Theta(q \cdot n)\) in the worst case, and both \(n\) and \(q\) can be \(10^5\). A legal trade’s net gain is the sum of two '0' runs separated by '1's, so the answer is the global number of '1's plus the best gain inside the query.

Adjacent pairs that lie wholly inside the interval can be queried in \(O(1)\) with a sparse table on the sums of neighboring run lengths. Residual runs that straddle \(l\) or \(r\) pair with the next full run or with each other. After storing each run as \((\textit{start},\textit{len})\), each query needs only a constant number of comparisons.

A valid trade picks two consecutive '0' runs separated by '1's, flips the '1's to '0's, then flips the merged '0' run back to '1's. The net gain is the sum of the two '0' run lengths, and the original number of '1's stays the same. Thus the answer for each query is the total number of '1's in \(s\), plus the maximum gain obtainable inside that query range.

Query \([l, r]\) may only operate on \(s[l..r]\), treated as \(t = \texttt{'1'} + s[l..r] + \texttt{'1'}\). Therefore:

  • Any pair of adjacent '0' runs completely inside the range is a candidate, with gain equal to the sum of their lengths;
  • If \(s[l]\) or \(s[r]\) lies in the middle of a '0' run, the suffix / prefix of that run inside the query range can also be paired.

We record every '0' run as \((\textit{start}, \textit{len})\) and build a sparse table on the sums of adjacent runs. For each query:

  1. Query the sparse table for the maximum adjacent-run sum fully inside the range;
  2. Also consider the leftover left run with the next run, the leftover right run with the previous run, and the special case where the two leftovers enclose a single '1' run.

Add the best gain to the global '1' count. If no trade is possible, the gain is \(0\).

Time complexity is \(O(n \log n + q)\), and space complexity is \(O(n \log n)\), where \(n\) is the length of \(s\) and \(q\) is the number of queries.

 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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution:
    def maxActiveSectionsAfterTrade(
        self, s: str, queries: List[List[int]]
    ) -> List[int]:
        n = len(s)
        active = s.count('1')
        if '0' not in s:
            return [active] * len(queries)

        zeros = []
        idx = [0] * n
        for i in range(n):
            if s[i] == '0':
                if i and s[i - 1] == '0':
                    zeros[-1][1] += 1
                else:
                    zeros.append([i, 1])
            idx[i] = len(zeros) - 1

        m = len(zeros) - 1
        K = m.bit_length() if m else 0
        st = [[0] * max(m, 0) for _ in range(max(K, 1))]
        for i in range(m):
            st[0][i] = zeros[i][1] + zeros[i + 1][1]
        for k in range(1, K):
            for i in range(m - (1 << k) + 1):
                st[k][i] = max(st[k - 1][i], st[k - 1][i + (1 << (k - 1))])

        def query(l: int, r: int) -> int:
            if l > r or m <= 0:
                return 0
            k = (r - l + 1).bit_length() - 1
            return max(st[k][l], st[k][r - (1 << k) + 1])

        ans = []
        for L, R in queries:
            iL, iR = idx[L], idx[R]
            cntL = -1 if iL < 0 else zeros[iL][1] - (L - zeros[iL][0])
            cntR = -1 if iR < 0 else R - zeros[iR][0] + 1
            start = iL + 1
            end = iR - (s[R] == '0')
            best = active
            if start < end:
                best = max(best, active + query(start, end - 1))
            if s[L] == '0' and s[R] == '0' and iL + 1 == iR:
                best = max(best, active + cntL + cntR)
            if s[L] == '0' and iL + 1 < iR + (s[R] == '1'):
                best = max(best, active + cntL + zeros[iL + 1][1])
            if s[R] == '0' and iL < iR - 1:
                best = max(best, active + cntR + zeros[iR - 1][1])
            ans.append(best)
        return ans

 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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
class Solution {
    public List<Integer> maxActiveSectionsAfterTrade(String s, int[][] queries) {
        int n = s.length();
        int active = 0;
        for (int i = 0; i < n; ++i) {
            if (s.charAt(i) == '1') {
                ++active;
            }
        }
        List<Integer> ans = new ArrayList<>();
        if (s.indexOf('0') < 0) {
            for (int i = 0; i < queries.length; ++i) {
                ans.add(active);
            }
            return ans;
        }

        int[][] zeros = new int[n][2];
        int z = 0;
        int[] idx = new int[n];
        for (int i = 0; i < n; ++i) {
            if (s.charAt(i) == '0') {
                if (i > 0 && s.charAt(i - 1) == '0') {
                    ++zeros[z - 1][1];
                } else {
                    zeros[z][0] = i;
                    zeros[z++][1] = 1;
                }
            }
            idx[i] = z - 1;
        }

        int m = z - 1;
        int K = m > 0 ? 32 - Integer.numberOfLeadingZeros(m) : 0;
        int[][] st = new int[Math.max(K, 1)][Math.max(m, 0)];
        for (int i = 0; i < m; ++i) {
            st[0][i] = zeros[i][1] + zeros[i + 1][1];
        }
        for (int k = 1; k < K; ++k) {
            for (int i = 0; i + (1 << k) <= m; ++i) {
                st[k][i] = Math.max(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
            }
        }

        for (int[] q : queries) {
            int L = q[0], R = q[1];
            int iL = idx[L], iR = idx[R];
            int cntL = iL < 0 ? -1 : zeros[iL][1] - (L - zeros[iL][0]);
            int cntR = iR < 0 ? -1 : R - zeros[iR][0] + 1;
            int start = iL + 1;
            int end = iR - (s.charAt(R) == '0' ? 1 : 0);
            int best = active;
            if (start < end) {
                best = Math.max(best, active + query(st, m, start, end - 1));
            }
            if (s.charAt(L) == '0' && s.charAt(R) == '0' && iL + 1 == iR) {
                best = Math.max(best, active + cntL + cntR);
            }
            if (s.charAt(L) == '0' && iL + 1 < iR + (s.charAt(R) == '1' ? 1 : 0)) {
                best = Math.max(best, active + cntL + zeros[iL + 1][1]);
            }
            if (s.charAt(R) == '0' && iL < iR - 1) {
                best = Math.max(best, active + cntR + zeros[iR - 1][1]);
            }
            ans.add(best);
        }
        return ans;
    }

    private int query(int[][] st, int m, int l, int r) {
        if (l > r || m <= 0) {
            return 0;
        }
        int k = 31 - Integer.numberOfLeadingZeros(r - l + 1);
        return Math.max(st[k][l], st[k][r - (1 << k) + 1]);
    }
}

 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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
class Solution {
public:
    vector<int> maxActiveSectionsAfterTrade(string s, vector<vector<int>>& queries) {
        int n = s.size();
        int active = count(s.begin(), s.end(), '1');
        if (s.find('0') == string::npos) {
            return vector<int>(queries.size(), active);
        }

        vector<pair<int, int>> zeros;
        vector<int> idx(n);
        for (int i = 0; i < n; ++i) {
            if (s[i] == '0') {
                if (i && s[i - 1] == '0') {
                    ++zeros.back().second;
                } else {
                    zeros.emplace_back(i, 1);
                }
            }
            idx[i] = (int) zeros.size() - 1;
        }

        int m = (int) zeros.size() - 1;
        int K = m ? 32 - __builtin_clz(m) : 0;
        vector<vector<int>> st(max(K, 1), vector<int>(max(m, 0)));
        for (int i = 0; i < m; ++i) {
            st[0][i] = zeros[i].second + zeros[i + 1].second;
        }
        for (int k = 1; k < K; ++k) {
            for (int i = 0; i + (1 << k) <= m; ++i) {
                st[k][i] = max(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
            }
        }

        auto query = [&](int l, int r) {
            if (l > r || m <= 0) {
                return 0;
            }
            int k = 31 - __builtin_clz(r - l + 1);
            return max(st[k][l], st[k][r - (1 << k) + 1]);
        };

        vector<int> ans;
        ans.reserve(queries.size());
        for (auto& q : queries) {
            int L = q[0], R = q[1];
            int iL = idx[L], iR = idx[R];
            int cntL = iL < 0 ? -1 : zeros[iL].second - (L - zeros[iL].first);
            int cntR = iR < 0 ? -1 : R - zeros[iR].first + 1;
            int start = iL + 1;
            int end = iR - (s[R] == '0');
            int best = active;
            if (start < end) {
                best = max(best, active + query(start, end - 1));
            }
            if (s[L] == '0' && s[R] == '0' && iL + 1 == iR) {
                best = max(best, active + cntL + cntR);
            }
            if (s[L] == '0' && iL + 1 < iR + (s[R] == '1')) {
                best = max(best, active + cntL + zeros[iL + 1].second);
            }
            if (s[R] == '0' && iL < iR - 1) {
                best = max(best, active + cntR + zeros[iR - 1].second);
            }
            ans.push_back(best);
        }
        return ans;
    }
};

 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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
func maxActiveSectionsAfterTrade(s string, queries [][]int) []int {
    n := len(s)
    active := 0
    for i := 0; i < n; i++ {
        if s[i] == '1' {
            active++
        }
    }
    if strings.IndexByte(s, '0') < 0 {
        ans := make([]int, len(queries))
        for i := range ans {
            ans[i] = active
        }
        return ans
    }

    zeros := make([][2]int, 0, n)
    idx := make([]int, n)
    for i := 0; i < n; i++ {
        if s[i] == '0' {
            if i > 0 && s[i-1] == '0' {
                zeros[len(zeros)-1][1]++
            } else {
                zeros = append(zeros, [2]int{i, 1})
            }
        }
        idx[i] = len(zeros) - 1
    }

    m := len(zeros) - 1
    K := 0
    if m > 0 {
        K = bits.Len(uint(m))
    }
    st := make([][]int, max(K, 1))
    for k := range st {
        st[k] = make([]int, max(m, 0))
    }
    for i := 0; i < m; i++ {
        st[0][i] = zeros[i][1] + zeros[i+1][1]
    }
    for k := 1; k < K; k++ {
        for i := 0; i+(1<<k) <= m; i++ {
            st[k][i] = max(st[k-1][i], st[k-1][i+(1<<(k-1))])
        }
    }

    query := func(l, r int) int {
        if l > r || m <= 0 {
            return 0
        }
        k := bits.Len(uint(r-l+1)) - 1
        return max(st[k][l], st[k][r-(1<<k)+1])
    }

    ans := make([]int, 0, len(queries))
    for _, q := range queries {
        L, R := q[0], q[1]
        iL, iR := idx[L], idx[R]
        cntL, cntR := -1, -1
        if iL >= 0 {
            cntL = zeros[iL][1] - (L - zeros[iL][0])
        }
        if iR >= 0 {
            cntR = R - zeros[iR][0] + 1
        }
        start := iL + 1
        end := iR
        if s[R] == '0' {
            end--
        }
        best := active
        if start < end {
            best = max(best, active+query(start, end-1))
        }
        if s[L] == '0' && s[R] == '0' && iL+1 == iR {
            best = max(best, active+cntL+cntR)
        }
        add := 0
        if s[R] == '1' {
            add = 1
        }
        if s[L] == '0' && iL+1 < iR+add {
            best = max(best, active+cntL+zeros[iL+1][1])
        }
        if s[R] == '0' && iL < iR-1 {
            best = max(best, active+cntR+zeros[iR-1][1])
        }
        ans = append(ans, best)
    }
    return ans
}

  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
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
impl Solution {
    pub fn max_active_sections_after_trade(s: String, queries: Vec<Vec<i32>>) -> Vec<i32> {
        let bytes = s.as_bytes();
        let length = bytes.len();
        let total_ones = bytes.iter().filter(|byte| **byte == b'1').count() as i32;
        if !bytes.contains(&b'0') {
            return vec![total_ones; queries.len()];
        }
        let mut zero_blocks: Vec<(usize, usize)> = Vec::new();
        let mut zero_block_at_position = Vec::with_capacity(length);
        for index in 0..length {
            if bytes[index] == b'0' {
                if index > 0 && bytes[index - 1] == b'0' {
                    zero_blocks.last_mut().unwrap().1 += 1;
                } else {
                    zero_blocks.push((index, 1usize));
                }
            }
            zero_block_at_position.push(zero_blocks.len() as isize - 1);
        }
        let zero_block_count = zero_blocks.len();
        let adjacent_pair_count = zero_block_count.saturating_sub(1);
        let sparse_level_count = if adjacent_pair_count == 0 {
            0
        } else {
            usize::BITS as usize - adjacent_pair_count.leading_zeros() as usize
        };
        let mut sparse_table = vec![0; adjacent_pair_count * sparse_level_count];
        for pair_index in 0..adjacent_pair_count {
            sparse_table[pair_index] =
                (zero_blocks[pair_index].1 + zero_blocks[pair_index + 1].1) as i32;
        }
        for level in 1..sparse_level_count {
            let half_span = 1usize << (level - 1);
            let span = 1usize << level;
            for start in 0..=adjacent_pair_count - span {
                sparse_table[level * adjacent_pair_count + start] = sparse_table
                    [(level - 1) * adjacent_pair_count + start]
                    .max(sparse_table[(level - 1) * adjacent_pair_count + start + half_span]);
            }
        }
        let max_pair_sum = |left_pair: usize, right_pair: usize| -> i32 {
            let right_pair = right_pair.min(adjacent_pair_count - 1);
            if left_pair > right_pair {
                return 0;
            }
            let level =
                usize::BITS as usize - (right_pair - left_pair + 1).leading_zeros() as usize - 1;
            let span = 1usize << level;
            sparse_table[level * adjacent_pair_count + left_pair]
                .max(sparse_table[level * adjacent_pair_count + right_pair - span + 1])
        };
        queries
            .into_iter()
            .map(|query| {
                let left = query[0] as usize;
                let right = query[1] as usize;
                let left_block_index = zero_block_at_position[left];
                let right_block_index = zero_block_at_position[right];
                let left_zero_count = if left_block_index == -1 {
                    -1
                } else {
                    let block_index = left_block_index as usize;
                    zero_blocks[block_index].1 as i32 - (left - zero_blocks[block_index].0) as i32
                };
                let right_zero_count = if right_block_index == -1 {
                    -1
                } else {
                    let block_index = right_block_index as usize;
                    (right - zero_blocks[block_index].0 + 1) as i32
                };
                let first_internal_pair = left_block_index + 1;
                let last_internal_pair = (if bytes[right] == b'1' {
                    right_block_index
                } else {
                    right_block_index - 1
                }) - 1;
                let last_full_zero_block = if bytes[right] == b'1' {
                    right_block_index
                } else {
                    right_block_index - 1
                };
                let mut best_total = total_ones;
                if bytes[left] == b'0'
                    && bytes[right] == b'0'
                    && left_block_index + 1 == right_block_index
                {
                    best_total = best_total.max(total_ones + left_zero_count + right_zero_count);
                } else if first_internal_pair <= last_internal_pair {
                    best_total = best_total.max(
                        total_ones
                            + max_pair_sum(
                                first_internal_pair as usize,
                                last_internal_pair as usize,
                            ),
                    );
                }
                if bytes[left] == b'0' && left_block_index + 1 <= last_full_zero_block {
                    best_total = best_total.max(
                        total_ones
                            + left_zero_count
                            + zero_blocks[(left_block_index + 1) as usize].1 as i32,
                    );
                }
                if bytes[right] == b'0' && left_block_index < right_block_index - 1 {
                    best_total = best_total.max(
                        total_ones
                            + right_zero_count
                            + zero_blocks[(right_block_index - 1) as usize].1 as i32,
                    );
                }
                best_total
            })
            .collect()
    }
}

Comments