3501. Maximize Active Section with Trade II Hard
1/**
2 * [3501] Maximize Active Section with Trade II
3 *
4 * You are given a binary string s of length n, where:
5 *
6 * '1' represents an active section.
7 * '0' represents an inactive section.
8 *
9 * You can perform at most one trade to maximize the number of active sections in s. In a trade, you:
10 *
11 * Convert a contiguous block of '1's that is surrounded by '0's to all '0's.
12 * Afterward, convert a contiguous block of '0's that is surrounded by '1's to all '1's.
13 *
14 * Additionally, you are given a 2D array queries, where queries[i] = [li, ri] represents a <span data-keyword="substring-nonempty">substring</span> s[li...ri].
15 * For each query, determine the maximum possible number of active sections in s after making the optimal trade on the substring s[li...ri].
16 * Return an array answer, where answer[i] is the result for queries[i].
17 * Note
18 *
19 * 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.
20 * The queries are independent of each other.
21 *
22 *
23 * <strong class="example">Example 1:
24 * <div class="example-block">
25 * Input: <span class="example-io">s = "01", queries = [[0,1]]</span>
26 * Output: <span class="example-io">[1]</span>
27 * Explanation:
28 * 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.
29 * </div>
30 * <strong class="example">Example 2:
31 * <div class="example-block">
32 * Input: <span class="example-io">s = "0100", queries = [[0,3],[0,2],[1,3],[2,3]]</span>
33 * Output: <span class="example-io">[4,3,1,1]</span>
34 * Explanation:
35 *
36 *
37 * Query [0, 3] → Substring "0100" → Augmented to "101001"<br />
38 * Choose "0100", convert "0100" → "0000" → "1111".<br />
39 * The final string without augmentation is "1111". The maximum number of active sections is 4.
40 *
41 *
42 * Query [0, 2] → Substring "010" → Augmented to "10101"<br />
43 * Choose "010", convert "010" → "000" → "111".<br />
44 * The final string without augmentation is "1110". The maximum number of active sections is 3.
45 *
46 *
47 * Query [1, 3] → Substring "100" → Augmented to "11001"<br />
48 * 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.
49 *
50 *
51 * Query [2, 3] → Substring "00" → Augmented to "1001"<br />
52 * 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.
53 *
54 * </div>
55 * <strong class="example">Example 3:
56 * <div class="example-block">
57 * Input: <span class="example-io">s = "1000100", queries = [[1,5],[0,6],[0,4]]</span>
58 * Output: <span class="example-io">[6,7,2]</span>
59 * Explanation:
60 *
61 * <li data-end="383" data-start="217">
62 * <p data-end="383" data-start="219">Query [1, 5] → Substring <code data-end="255" data-start="246">"00010" → Augmented to <code data-end="282" data-start="271">"1000101"<br data-end="285" data-start="282" />
63 * Choose <code data-end="303" data-start="294">"00010", convert <code data-end="322" data-start="313">"00010" → <code data-end="322" data-start="313">"00000" → <code data-end="334" data-start="325">"11111".<br />
64 * The final string without augmentation is <code data-end="404" data-start="396">"1111110". The maximum number of active sections is 6.
65 *
66 * <li data-end="561" data-start="385">
67 * <p data-end="561" data-start="387">Query [0, 6] → Substring <code data-end="425" data-start="414">"1000100" → Augmented to <code data-end="454" data-start="441">"110001001"<br data-end="457" data-start="454" />
68 * Choose <code data-end="477" data-start="466">"000100", convert <code data-end="498" data-start="487">"000100" → <code data-end="498" data-start="487">"000000" → <code data-end="512" data-start="501">"111111".<br />
69 * The final string without augmentation is <code data-end="404" data-start="396">"1111111". The maximum number of active sections is 7.
70 *
71 * <li data-end="741" data-start="563">
72 * <p data-end="741" data-start="565">Query [0, 4] → Substring <code data-end="601" data-start="592">"10001" → Augmented to <code data-end="627" data-start="617">"1100011"<br data-end="630" data-start="627" />
73 * 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.
74 *
75 * </div>
76 * <strong class="example">Example 4:
77 * <div class="example-block">
78 * Input: <span class="example-io">s = "01010", queries = [[0,3],[1,4],[1,3]]</span>
79 * Output: <span class="example-io">[4,4,2]</span>
80 * Explanation:
81 *
82 *
83 * Query [0, 3] → Substring "0101" → Augmented to "101011"<br />
84 * Choose "010", convert "010" → "000" → "111".<br />
85 * The final string without augmentation is "11110". The maximum number of active sections is 4.
86 *
87 *
88 * Query [1, 4] → Substring "1010" → Augmented to "110101"<br />
89 * Choose "010", convert "010" → "000" → "111".<br />
90 * The final string without augmentation is "01111". The maximum number of active sections is 4.
91 *
92 *
93 * Query [1, 3] → Substring "101" → Augmented to "11011"<br />
94 * 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.
95 *
96 * </div>
97 *
98 * Constraints:
99 *
100 * 1 <= n == s.length <= 10^5
101 * 1 <= queries.length <= 10^5
102 * s[i] is either '0' or '1'.
103 * queries[i] = [li, ri]
104 * 0 <= li <= ri < n
105 *
106 */
107pub struct Solution {}
108
109// problem: https://leetcode.com/problems/maximize-active-section-with-trade-ii/
110// discuss: https://leetcode.com/problems/maximize-active-section-with-trade-ii/discuss/?currentPage=1&orderBy=most_votes&query=
111
112// submission codes start here
113
114impl Solution {
115 pub fn max_active_sections_after_trade(s: String, queries: Vec<Vec<i32>>) -> Vec<i32> {
116 vec![]
117 }
118}
119
120// submission codes end
121
122#[cfg(test)]
123mod tests {
124 use super::*;
125
126 #[test]
127 fn test_3501() {
128 }
129}
130Back
© 2026 bowen.ge All Rights Reserved.