Maximize Active Section with Trade II

Hard

#3113Time: 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.

Algorithms

Binary Search

Data structures

Array String Segment Tree

Prompt

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] = [l_i, r_i] represents a substring s[l_i...r_i].

For each query, determine the maximum possible number of active sections in s after making the optimal trade on the substring s[l_i...r_i].

Return an array answer, where answer[i] is the result for queries[i].

Note

For each query, treat s[l_i...r_i] as if it is augmented with a '1' at both ends, forming t = '1' + s[l_i...r_i] + '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 <= 10⁵
1 <= queries.length <= 10⁵
s[i] is either '0' or '1'.
queries[i] = [l_i, r_i]
0 <= l_i <= r_i < n

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

The core of this method is a loop that iterates through each query. Inside the loop, we perform the following steps:

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.
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.
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.
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.

1class Solution {2    public int[] maximizeActiveSection(String s, int[][] queries) {3        int n = s.length();4        int totalOnes = 0;5        for (char c : s.toCharArray()) {6            if (c == '1') {7                totalOnes++;8            }9        }10 11        int[] answer = new int[queries.length];12        for (int i = 0; i < queries.length; i++) {13            int l = queries[i][0];14            int r = queries[i][1];15 16            String sub = s.substring(l, r + 1);17            String t = "1" + sub + "1";18 19            List<int[]> blocks = new ArrayList<>();20            if (t.length() > 0) {21                blocks.add(new int[]{t.charAt(0) - '0', 1});22                for (int j = 1; j < t.length(); j++) {23                    if (t.charAt(j) - '0' == blocks.get(blocks.size() - 1)[0]) {24                        blocks.get(blocks.size() - 1)[1]++;25                    } else {26                        blocks.add(new int[]{t.charAt(j) - '0', 1});27                    }28                }29            }30 31            int maxGain = 0;32            // An internal '1'-block is at an odd index (1-based) in the blocks list33            // e.g., C1, Z1, C2, Z2, C3 -> indices 0,1,2,3,4. C2 is at index 2.34            // We need blocks[i-1], blocks[i], blocks[i+1] where blocks[i] is a '1'-block.35            for (int j = 1; j < blocks.size() - 1; j++) {36                if (blocks.get(j)[0] == 1) { // If it's a '1'-block37                    // It must be surrounded by '0'-blocks38                    if (blocks.get(j - 1)[0] == 0 && blocks.get(j + 1)[0] == 0) {39                        int gain = blocks.get(j - 1)[1] + blocks.get(j + 1)[1];40                        maxGain = Math.max(maxGain, gain);41                    }42                }43            }44            answer[i] = totalOnes + maxGain;45        }46        return answer;47    }48}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

This advanced approach avoids re-computation by processing queries in a batch.

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)).
Data Organization: We use maps to group triplets and queries by their respective end coordinates. Map<Integer, List<Triplet>> tripletsByEnd and Map<Integer, List<Query>> queriesByR.
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.

1class Solution {2    // Query and Triplet helper classes would be defined here or as records.3    // SegmentTree class for Range Maximum Query is also needed.4 5    public int[] maximizeActiveSection(String s, int[][] queries) {6        int n = s.length();7        int totalOnes = 0;8        for (char c : s.toCharArray()) {9            if (c == '1') totalOnes++;10        }11 12        // 1. Pre-computation: Find all blocks and triplets13        List<int[]> blocks = new ArrayList<>();14        if (n > 0) {15            blocks.add(new int[]{s.charAt(0) - '0', 1, 0}); // type, len, start_idx16            for (int i = 1; i < n; i++) {17                if (s.charAt(i) - '0' == blocks.get(blocks.size() - 1)[0]) {18                    blocks.get(blocks.size() - 1)[1]++;19                } else {20                    blocks.add(new int[]{s.charAt(i) - '0', 1, i});21                }22            }23        }24 25        Map<Integer, List<Triplet>> tripletsByEnd = new HashMap<>();26        for (int i = 1; i < blocks.size() - 1; i++) {27            if (blocks.get(i)[0] == 1) { // '1'-block28                if (blocks.get(i - 1)[0] == 0 && blocks.get(i + 1)[0] == 0) {29                    int[] z_l = blocks.get(i - 1);30                    int[] z_r = blocks.get(i + 1);31                    int start = z_l[2];32                    int end = z_r[2] + z_r[1] - 1;33                    int gain = z_l[1] + z_r[1];34                    tripletsByEnd.computeIfAbsent(end, k -> new ArrayList<>()).add(new Triplet(start, end, gain));35                }36            }37        }38 39        // 2. Offline Processing40        Map<Integer, List<Query>> queriesByR = new HashMap<>();41        for (int i = 0; i < queries.length; i++) {42            queriesByR.computeIfAbsent(queries[i][1], k -> new ArrayList<>()).add(new Query(queries[i][0], queries[i][1], i));43        }44 45        int[] answer = new int[queries.length];46        SegmentTree st = new SegmentTree(n);47 48        for (int r = 0; r < n; r++) {49            // Add triplets ending at r to segment tree50            if (tripletsByEnd.containsKey(r)) {51                for (Triplet t : tripletsByEnd.get(r)) {52                    st.update(0, 0, n - 1, t.start, t.gain);53                }54            }55 56            // Process queries ending at r57            if (queriesByR.containsKey(r)) {58                for (Query q : queriesByR.get(r)) {59                    int maxGain = st.query(0, 0, n - 1, q.l, n - 1);60                    answer[q.index] = totalOnes + maxGain;61                }62            }63        }64 65        return answer;66    }67}68 69// Helper classes (records for modern Java)70record Query(int l, int r, int index) {}71record Triplet(int start, int end, int gain) {}72 73class SegmentTree {74    int[] tree;75    int n;76    public SegmentTree(int size) {77        n = size;78        tree = new int[4 * n];79    }80    public void update(int node, int start, int end, int idx, int val) {81        if (start == end) {82            tree[node] = Math.max(tree[node], val);83            return;84        }85        int mid = start + (end - start) / 2;86        if (start <= idx && idx <= mid) {87            update(2 * node + 1, start, mid, idx, val);88        } else {89            update(2 * node + 2, mid + 1, end, idx, val);90        }91        tree[node] = Math.max(tree[2 * node + 1], tree[2 * node + 2]);92    }93    public int query(int node, int start, int end, int l, int r) {94        if (r < start || end < l || l > r) return 0;95        if (l <= start && end <= r) return tree[node];96        int mid = start + (end - start) / 2;97        int p1 = query(2 * node + 1, start, mid, l, r);98        int p2 = query(2 * node + 2, mid + 1, end, l, r);99        return Math.max(p1, p2);100    }101}

Complexity

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.

Trade-offs

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.

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem