Maximize Active Sections After One Trade
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
A binary string `s` describes sections: `1` is active and `0` is inactive. You may perform at most one **trade**, consisting of these two steps in order:
1. Choose a contiguous block of `1`s surrounded immediately by `0`s, and change the entire block to `0`s.
2. In the resulting string, choose a contiguous block of `0`s surrounded immediately by `1`s, and change the entire block to `1`s.
For deciding whether a block is surrounded, treat the string as `"1" + s + "1"`. These two added boundary characters are not part of the original string and do not contribute to its active-section count.
Return the greatest number of active sections in the original string after at most one trade. You may also leave the string unchanged. A trade requires both steps; performing only the second step is not allowed.
### C++ Interface
```cpp
class Solution {
public:
int maxActiveSectionsAfterTrade(string s) {
}
};
```
### Examples
**Example 1**
```text
Input: s = "0011000"
Output: 7
```
The two middle `1`s are surrounded by `0`s. Changing them to zero makes all seven original characters zero. With the added boundary `1`s, that zero block is surrounded by ones and can be changed to seven active sections. No result can exceed the string length.
**Example 2**
```text
Input: s = "1001"
Output: 2
```
Neither original block of `1`s is surrounded by zeros when the added boundary ones are included. No first step is legal, so no trade can be completed. The two existing active sections remain.
### Constraints
- `1 <= n == s.length <= 100000`.
- Every `s[i]` is either `0` or `1`.
### Clarifying Questions
- May the two steps be reversed? No. The one-block conversion must happen first.
- Are the added boundary ones counted? No. They only define which blocks are surrounded.
- Must a trade be performed? No. At most one is allowed.
- Must the final string be returned? No. Return only the largest possible active count.
### What a Strong Answer Covers
- The exact two-step operation and the string state used for each step.
- The added boundary characters and their exclusion from the returned count.
- The option of doing nothing when a trade is unavailable or unnecessary.
- A proof of optimality and bounds for the full input length.
### Follow-up Questions
- Why does an all-zero string still have no legal trade under the specified two-step rule?
- Would counting the two added characters change the task's requested result?
```hint Measure a complete trade
Separate maximal runs of zeros and ones. Removing an internal one-run joins its two neighboring zero-runs; flipping that joined run restores the removed ones as well. Consider the net change in the original active count.
```
Overview: Maximize the active count of a binary string after at most one complete two-step trade. Preserve the required operation order and exclude the added boundary ones from the result.