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.

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