Independent Active-Section Trade Queries
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
You are given a binary string `s`, where `1` marks an active section and `0` marks an inactive section, and inclusive, zero-based queries `[l, r]`.
For each query independently, you may perform at most one trade entirely within `s[l...r]`. A trade has two ordered steps:
1. Change a contiguous block of `1`s immediately surrounded by `0`s into zeros.
2. In the resulting substring, change a contiguous block of `0`s immediately surrounded by `1`s into ones.
For this query's surrounding-character checks, treat its substring as `"1" + s[l...r] + "1"`. The added ones are not original sections and are not counted.
Return one answer per query: the maximum number of active sections in the **whole string `s`** after that query's allowed trade. Characters outside `[l,r]` remain unchanged. Queries do not accumulate changes; each starts with the original string. Performing no trade is allowed, but performing only the second step is not.
### C++ Interface
```cpp
class Solution {
public:
vector<int> maxActiveSectionsAfterTrade(string s, vector<vector<int>>& queries) {
}
};
```
### Examples
**Example 1**
```text
Input: s = "0011000100", queries = [[0,9],[1,8],[2,7],[4,9]]
Output: [8,7,3,8]
```
The original string has three ones. For `[0,9]`, changing the ones at indices `2,3` to zero and then changing indices `0...6` to one gives eight active sections. For `[1,8]`, the same first step followed by changing indices `1...6` to one gives seven. Query `[2,7]` permits no legal first step and leaves the global count at three. For `[4,9]`, trading the one at index `7` makes that entire six-character substring active; the two ones outside it bring the answer to eight.
**Example 2**
```text
Input: s = "110010001", queries = [[0,8],[3,6],[0,3],[5,5]]
Output: [9,7,4,4]
```
The original global count is four. In `[0,8]`, trading the one at index `4` can make the whole string active. In `[3,6]`, the substring is `"0100"`; completing its trade makes its four positions active, while three original ones outside the query remain, giving seven. Neither `[0,3]` nor `[5,5]` allows a first step, so their answers remain four.
### Constraints
- `1 <= n == s.length <= 100000`.
- `1 <= queries.length <= 100000`.
- Every `s[i]` is `0` or `1`.
- Each query contains exactly two integers `[l, r]`.
- `0 <= l <= r < n`.
### Clarifying Questions
- Does an answer count only ones inside the queried substring? No. It counts the whole string after changing only that substring.
- Do actual characters just outside the query determine whether its edge blocks are surrounded? No. Use the query's two added boundary ones.
- Do earlier answers change the string for later queries? No. All queries are independent.
- What happens if no trade is legal? Return the original string's active count for that query.
### What a Strong Answer Covers
- Both ordered trade steps, their legality inside the queried substring, and the option of no trade.
- Query-specific surrounding characters and their exclusion from the count.
- The whole-string answer and independence of different queries.
- Single-position queries, queries reaching string edges, and the maximum string and query counts.
- An optimality argument and suitable time, space, and numeric bounds.
### Follow-up Questions
- Can a query containing only zeros still have a positive answer under this whole-string counting rule?
- Which part of the specification would change if query effects were cumulative instead of independent?
```hint Reuse the unchanged string
Describe the string by its maximal zero and one runs. A trade that removes an internal one-run can gain the lengths of its two neighboring zero-runs. Precompute range maxima for fully included neighboring pairs, and handle zero-runs clipped by a query boundary separately.
```
Overview: Answer independent binary-string trade queries while counting active sections across the whole string. Restrict both trade steps to each substring and preserve its virtual boundary rules.