# Maximize Active Section with Trade II **Difficulty:** HARD [External](https://leetcode.com/problems/maximize-active-section-with-trade-ii) Canonical: https://scaleengineer.com/dsa/problems/maximize-active-section-with-trade-ii **Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search) **Data structures:** Array, String, Segment Tree --- ## 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:** **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` # Approaches ## Brute-Force Simulation per Query This approach directly simulates the process described in the problem for each query. It involves constructing the augmented substring for every query, parsing it into blocks of consecutive '0's and '1's, and then calculating the best possible trade. The optimal trade is found by realizing that sacrificing an internal '1'-block allows for the merging of its two neighboring '0'-blocks, and the sum of their lengths represents the net gain in '1's. By iterating through all possible '1'-blocks that can be sacrificed, we find the maximum gain. **Time:** O(Q * N), where Q is the number of queries and N is the length of `s`. For each query, we might process a substring of length up to N. Given the constraints (N, Q <= 10^5), this is too slow. · **Space:** O(N) for each query in the worst case, where N is the length of `s`. This is because the substring and its block representation can be of length up to N. **Pros:** Simple to understand and implement.; Correctly solves the problem for small inputs. **Cons:** Highly inefficient due to repetitive work. For each query, it re-processes a substring, which can be up to length `N`.; Will result in a 'Time Limit Exceeded' (TLE) error on platforms with large test cases due to its high time complexity. ### Explanation The core of this method is a loop that iterates through each query. Inside the loop, we perform the following steps: 1. **Isolate Substring and Augment:** For a query `[l, r]`, we form the string `t = '1' + s.substring(l, r + 1) + '1'`. This `t` is the basis for all trade calculations for the current query. 2. **Block Parsing:** We scan through `t` to identify its block structure. We can store this as a list of pairs, where each pair contains the character ('0' or '1') and the length of the block. 3. **Calculate Maximum Gain:** We iterate through the list of blocks. A trade is possible if we can find a '1'-block that is preceded and succeeded by a '0'-block (an internal '1'-block). For each such '1'-block, the potential gain is the sum of the lengths of its neighboring '0'-blocks. We keep track of the maximum such gain found. 4. **Compute Final Answer:** The result for the query is the total number of '1's in the original string `s` plus the maximum gain calculated. If no valid trade is possible, the gain is zero. ```java class Solution { public int[] maximizeActiveSection(String s, int[][] queries) { int n = s.length(); int totalOnes = 0; for (char c : s.toCharArray()) { if (c == '1') { totalOnes++; } } int[] answer = new int[queries.length]; for (int i = 0; i < queries.length; i++) { int l = queries[i][0]; int r = queries[i][1]; String sub = s.substring(l, r + 1); String t = "1" + sub + "1"; List blocks = new ArrayList<>(); if (t.length() > 0) { blocks.add(new int[]{t.charAt(0) - '0', 1}); for (int j = 1; j < t.length(); j++) { if (t.charAt(j) - '0' == blocks.get(blocks.size() - 1)[0]) { blocks.get(blocks.size() - 1)[1]++; } else { blocks.add(new int[]{t.charAt(j) - '0', 1}); } } } int maxGain = 0; // An internal '1'-block is at an odd index (1-based) in the blocks list // e.g., C1, Z1, C2, Z2, C3 -> indices 0,1,2,3,4. C2 is at index 2. // We need blocks[i-1], blocks[i], blocks[i+1] where blocks[i] is a '1'-block. for (int j = 1; j < blocks.size() - 1; j++) { if (blocks.get(j)[0] == 1) { // If it's a '1'-block // It must be surrounded by '0'-blocks if (blocks.get(j - 1)[0] == 0 && blocks.get(j + 1)[0] == 0) { int gain = blocks.get(j - 1)[1] + blocks.get(j + 1)[1]; maxGain = Math.max(maxGain, gain); } } } answer[i] = totalOnes + maxGain; } return answer; } } ``` ### Algorithm * **Overall Idea:** For each query, simulate the process directly. Construct the augmented substring and analyze its block structure to find the maximum possible gain from a trade. * **Initial Setup:** 1. Calculate the total number of '1's in the original string `s`. Let this be `totalOnes`. This will be the base for our answers. * **Per-Query Processing:** For each query `[l, r]`: 1. Extract the substring `s[l...r]`. 2. Create the augmented string `t = '1' + s[l...r] + '1'`. The length of `t` is `(r - l + 1) + 2`. 3. Parse `t` to identify all contiguous blocks of '0's and '1's. For example, `t = "1001101"` would be parsed into blocks: `(1, len=1)`, `(0, len=2)`, `(1, len=2)`, `(0, len=1)`, `(1, len=1)`. 4. Let the block structure of `t` be `C_1, Z_1, C_2, Z_2, ..., C_k, Z_k, C_{k+1}`, where `C_i` are '1'-blocks and `Z_i` are '0'-blocks. 5. A trade involves sacrificing an internal '1'-block `C_i` (where `1 < i <= k`) which is surrounded by '0'-blocks `Z_{i-1}` and `Z_i`. This sacrifice merges `Z_{i-1}` and `Z_i` with the space of `C_i`, creating a new large '0'-block of length `len(Z_{i-1}) + len(C_i) + len(Z_i)`. This new block is surrounded by '1's (from `C_{i-1}` and `C_{i+1}`) and can be converted to '1's. 6. The net gain from this operation is `(len(Z_{i-1}) + len(C_i) + len(Z_i)) - len(C_i) = len(Z_{i-1}) + len(Z_i)`. 7. To maximize the total number of '1's, we should find the maximum possible gain. Iterate through all internal '1'-blocks `C_i` (from `i=2` to `k`) and calculate `gain_i = len(Z_{i-1}) + len(Z_i)`. The maximum of these is the `maxGain` for the query. 8. If there are no internal '1'-blocks (`k <= 1`), no trade is possible, and `maxGain` is 0. 9. The answer for the query is `totalOnes + maxGain`. * **Return Value:** An array containing the calculated answer for each query. ## Offline Processing with Sweep-line and Segment Tree A brute-force approach is too slow because it recomputes the same information for overlapping queries. A much more efficient method is to process queries offline. The key insight is that the maximum gain for a query `[l, r]` comes from a `0-1-0` block pattern (a triplet) that is fully contained within `s[l...r]`. The problem then becomes: for each query `[l, r]`, find the triplet `(start, end, gain)` such that `l <= start`, `end <= r`, and `gain` is maximized. This is a 2D range maximum query problem. We can solve it efficiently in quasi-linear time by using a sweep-line algorithm. We sort both queries and triplets by their end points. As we sweep a line from left to right across the string, we add triplets to a data structure (a segment tree) as we encounter their end points. For each query ending at the current sweep-line position, we query the data structure to find the best triplet that satisfies the start condition. **Time:** O((N + Q) log N). Pre-computation takes O(N). The sweep-line algorithm involves O(N) updates and O(Q) queries on the segment tree, each taking O(log N) time. · **Space:** O(N + Q), where N is for the segment tree and block/triplet storage, and Q is for storing the queries. **Pros:** Very efficient, capable of handling large inputs within time limits.; Scales well with the number of queries and the length of the string.; Avoids redundant computations by processing queries in a structured, offline manner. **Cons:** More complex to implement, requiring knowledge of advanced data structures like segment trees and offline algorithms.; Higher constant factor in time complexity compared to a simpler (but less efficient) approach. ### Explanation This advanced approach avoids re-computation by processing queries in a batch. 1. **Triplet Identification:** We first scan `s` and create a list of all `(Z_L, C, Z_R)` triplets. For each, we store its start index in `s`, end index, and the calculated gain (`len(Z_L) + len(Z_R)`). 2. **Data Organization:** We use maps to group triplets and queries by their respective end coordinates. `Map> tripletsByEnd` and `Map> queriesByR`. 3. **Sweep-line and Segment Tree:** We use a segment tree designed for range maximum queries. The tree will operate on indices `0` to `N-1`. * We iterate `r` from `0` to `N-1`. * At each `r`, we look up `tripletsByEnd.get(r)`. For each triplet found, we update our segment tree at its `start` index with its `gain`. * Then, we look up `queriesByR.get(r)`. For each query, we use the segment tree to find the maximum gain in its valid start range, `[l, N-1]`. The query `segmentTree.query(l, N-1)` gives the max gain for a triplet whose `start >= l` and `end <= r`. * The answer is `totalOnes` (pre-calculated) plus this max gain. ```java class Solution { // Query and Triplet helper classes would be defined here or as records. // SegmentTree class for Range Maximum Query is also needed. public int[] maximizeActiveSection(String s, int[][] queries) { int n = s.length(); int totalOnes = 0; for (char c : s.toCharArray()) { if (c == '1') totalOnes++; } // 1. Pre-computation: Find all blocks and triplets List blocks = new ArrayList<>(); if (n > 0) { blocks.add(new int[]{s.charAt(0) - '0', 1, 0}); // type, len, start_idx for (int i = 1; i < n; i++) { if (s.charAt(i) - '0' == blocks.get(blocks.size() - 1)[0]) { blocks.get(blocks.size() - 1)[1]++; } else { blocks.add(new int[]{s.charAt(i) - '0', 1, i}); } } } Map> tripletsByEnd = new HashMap<>(); for (int i = 1; i < blocks.size() - 1; i++) { if (blocks.get(i)[0] == 1) { // '1'-block if (blocks.get(i - 1)[0] == 0 && blocks.get(i + 1)[0] == 0) { int[] z_l = blocks.get(i - 1); int[] z_r = blocks.get(i + 1); int start = z_l[2]; int end = z_r[2] + z_r[1] - 1; int gain = z_l[1] + z_r[1]; tripletsByEnd.computeIfAbsent(end, k -> new ArrayList<>()).add(new Triplet(start, end, gain)); } } } // 2. Offline Processing Map> queriesByR = new HashMap<>(); for (int i = 0; i < queries.length; i++) { queriesByR.computeIfAbsent(queries[i][1], k -> new ArrayList<>()).add(new Query(queries[i][0], queries[i][1], i)); } int[] answer = new int[queries.length]; SegmentTree st = new SegmentTree(n); for (int r = 0; r < n; r++) { // Add triplets ending at r to segment tree if (tripletsByEnd.containsKey(r)) { for (Triplet t : tripletsByEnd.get(r)) { st.update(0, 0, n - 1, t.start, t.gain); } } // Process queries ending at r if (queriesByR.containsKey(r)) { for (Query q : queriesByR.get(r)) { int maxGain = st.query(0, 0, n - 1, q.l, n - 1); answer[q.index] = totalOnes + maxGain; } } } return answer; } } // Helper classes (records for modern Java) record Query(int l, int r, int index) {} record Triplet(int start, int end, int gain) {} class SegmentTree { int[] tree; int n; public SegmentTree(int size) { n = size; tree = new int[4 * n]; } public void update(int node, int start, int end, int idx, int val) { if (start == end) { tree[node] = Math.max(tree[node], val); return; } int mid = start + (end - start) / 2; if (start <= idx && idx <= mid) { update(2 * node + 1, start, mid, idx, val); } else { update(2 * node + 2, mid + 1, end, idx, val); } tree[node] = Math.max(tree[2 * node + 1], tree[2 * node + 2]); } public int query(int node, int start, int end, int l, int r) { if (r < start || end < l || l > r) return 0; if (l <= start && end <= r) return tree[node]; int mid = start + (end - start) / 2; int p1 = query(2 * node + 1, start, mid, l, r); int p2 = query(2 * node + 2, mid + 1, end, l, r); return Math.max(p1, p2); } } ``` ### Algorithm * **Overall Idea:** The problem asks for the maximum gain within a query range `[l, r]`. This can be framed as a range query problem. We can process all queries together (offline) using a sweep-line algorithm combined with a segment tree to answer them efficiently. * **Pre-computation:** 1. First, parse the entire string `s` to identify all its contiguous blocks of '0's and '1's. 2. Identify all "triplets" of the form `(Z_L, C, Z_R)`, where `C` is a '1'-block and `Z_L`, `Z_R` are its immediate left and right '0'-block neighbors in `s`. 3. For each such triplet, calculate its properties: * `start`: The starting index of the triplet in `s` (which is `Z_L.start`). * `end`: The ending index of the triplet in `s` (which is `Z_R.end`). * `gain`: The potential gain from this triplet, which is `len(Z_L) + len(Z_R)`. 4. Store these triplets. A triplet is a valid candidate for a trade in query `[l, r]` if `l <= start` and `end <= r`. * **Offline Processing (Sweep-line):** 1. Store all queries and triplets in data structures, grouped by their `end` index. 2. Initialize a segment tree of size `N`. This segment tree will store maximum gain values, indexed by the `start` index of triplets. 3. Initialize an `answer` array for the queries. 4. Iterate a "sweep-line" `i` from `0` to `N-1`: a. For the current position `i`, find all triplets that have `end == i`. For each such triplet `(start, end, gain)`, update the segment tree: `segmentTree.update(start, gain)`. The update operation ensures that `segmentTree[start]` holds the maximum gain among all triplets starting at `start` and ending at or before `i`. b. Now, find all queries that have `r == i`. For each such query `(l, r, query_idx)`, query the segment tree for the maximum value in the range `[l, N-1]`. This query `segmentTree.query(l, N-1)` efficiently finds `max{gain}` over all triplets `(start, end, gain)` such that `l <= start` and `end <= i` (which is the current `r`). c. Store the result (`totalOnes + maxGain`) in `answer[query_idx]`. * **Final Result:** The `answer` array holds the results for all queries.