# Maximize Active Section with Trade I
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximize-active-section-with-trade-i)
Canonical: https://scaleengineer.com/dsa/problems/maximize-active-section-with-trade-i
**Patterns:** [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** String
---
## 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.

Return the **maximum** number of active sections in `s` after making the optimal trade.

**Note:** Treat `s` as if it is **augmented** with a `'1'` at both ends, forming `t = '1' + s + '1'`. The augmented `'1'`s **do not** contribute to the final count.

**Example 1:**

**Input:** s = "01"

**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"

**Output:** 4

**Explanation:**

* String `"0100"` → Augmented to `"101001"`.
* Choose `"0100"`, convert `"10**1**001"` → `"1**0000**1"` → `"1**1111**1"`.
* The final string without augmentation is `"1111"`. The maximum number of active sections is 4.

**Example 3:**

**Input:** s = "1000100"

**Output:** 7

**Explanation:**

* String `"1000100"` → Augmented to `"110001001"`.
* Choose `"000100"`, convert `"11000**1**001"` → `"11**000000**1"` → `"11**111111**1"`.
* The final string without augmentation is `"1111111"`. The maximum number of active sections is 7.

**Example 4:**

**Input:** s = "01010"

**Output:** 4

**Explanation:**

* String `"01010"` → Augmented to `"1010101"`.
* Choose `"010"`, convert `"10**1**0101"` → `"1**000**101"` → `"1**111**101"`.
* The final string without augmentation is `"11110"`. The maximum number of active sections is 4.

**Constraints:**

* `1 <= n == s.length <= 105`
* `s[i]` is either `'0'` or `'1'`

# Approaches
## Block Grouping and Analysis
This approach directly translates the problem's structure into code. The key insight is that the net gain from a trade is determined by the lengths of the '0' blocks adjacent to the '1' block being traded. By converting the augmented string `t` into a sequence of homogeneous blocks (e.g., `"11001"` becomes `[('1', 2), ('0', 2), ('1', 1)]`), we can easily identify all internal '1' blocks and their neighboring '0' blocks. We then iterate through these internal '1' blocks, calculate the potential gain for each, and find the maximum possible gain to add to the initial count of ones.
**Time:** O(N), where N is the length of the string `s`. Calculating initial ones, building the augmented string, parsing into blocks, and iterating through the blocks all take linear time. · **Space:** O(N), where N is the length of the string `s`. This is because we store the augmented string `t` (O(N)) and the list of blocks, which in the worst case (e.g., "010101...") can have O(N) elements.
**Pros:** Intuitive and directly models the problem by representing the string as a sequence of blocks.; Relatively easy to implement and understand.
**Cons:** Requires O(N) extra space to store the list of blocks, which can be up to N+2 blocks for a highly alternating string.
### Explanation
```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int maximizeActiveSections(String s) {
        int n = s.length();
        String t = "1" + s + "1";
        
        int initialOnes = 0;
        for (char c : s.toCharArray()) {
            if (c == '1') {
                initialOnes++;
            }
        }

        // Group t into blocks of consecutive identical characters
        List<int[]> blocks = new ArrayList<>();
        int p = 0;
        while (p < t.length()) {
            char type = t.charAt(p);
            int start = p;
            while (p < t.length() && t.charAt(p) == type) {
                p++;
            }
            // block[0] is type (0 or 1), block[1] is length
            blocks.add(new int[]{type - '0', p - start});
        }

        int maxGain = 0;
        // An internal '1' block must have '0' blocks on both sides.
        // This means we need at least 3 blocks (0-1-0 pattern).
        if (blocks.size() < 3) {
            return initialOnes;
        }

        // Iterate through blocks to find internal '1' blocks
        for (int i = 1; i < blocks.size() - 1; i++) {
            // If blocks.get(i) is a '1' block, its neighbors at i-1 and i+1 must be '0' blocks.
            if (blocks.get(i)[0] == 1) {
                int gain = blocks.get(i - 1)[1] + blocks.get(i + 1)[1];
                maxGain = Math.max(maxGain, gain);
            }
        }

        return initialOnes + maxGain;
    }
}
```
### Algorithm
*   **Core Idea:** The problem asks to maximize the number of active sections ('1's) by performing at most one trade. A trade involves swapping a block of '1's for a block of '0's. The net change in the count of '1's is `(length of '0' block gained) - (length of '1' block given up)`. Analyzing the trade process reveals that when we give up an internal '1' block, it merges with its two neighboring '0' blocks, creating a single large '0' block which can then be flipped to '1's. The net gain from this operation is simply the sum of the lengths of the two original neighboring '0' blocks.
*   **Algorithm Steps:**
    1.  Construct the augmented string `t = '1' + s + '1'`. This simplifies boundary conditions.
    2.  Calculate the initial number of '1's in the original string `s`.
    3.  Parse the augmented string `t` into a list of contiguous blocks, storing each block's type ('0' or '1') and length.
    4.  Initialize a `maxGain` variable to 0.
    5.  Iterate through the list of blocks. For each '1' block that is not the first or the last block (i.e., it's an internal block), its neighbors must be '0' blocks.
    6.  Calculate the potential gain for trading this '1' block, which is the sum of the lengths of its left and right neighboring '0' blocks.
    7.  Update `maxGain` with the maximum gain found so far.
    8.  The final result is the `initialOnes + maxGain`.

## Dynamic Programming with Prefix/Suffix Arrays
This approach uses a common dynamic programming technique to solve problems involving contiguous segments. By pre-calculating the lengths of same-character runs from both the left and the right for every position, we can quickly query the necessary information. For any potential '1' block we want to trade, we can find the lengths of its neighboring '0' blocks in O(1) time using the precomputed arrays. This avoids the overhead of creating a list of block objects and provides a systematic way to find the optimal trade.
**Time:** O(N), where N is the length of `s`. Each step, including the creation of `L` and `R` arrays and the final iteration, takes linear time. · **Space:** O(N), where N is the length of `s`. The space is dominated by the `L` and `R` arrays and the temporary string `t`, all of which are proportional to N.
**Pros:** Efficient O(N) time complexity.; Uses a standard dynamic programming pattern (prefix/suffix computations) that is applicable to many similar problems.
**Cons:** Requires O(N) extra space for the auxiliary arrays `L` and `R`.; Slightly less direct than the block grouping approach as it works on indices rather than whole blocks.
### Explanation
```java
class Solution {
    public int maximizeActiveSections(String s) {
        int n = s.length();
        String t = "1" + s + "1";
        int nt = t.length();
        
        int initialOnes = 0;
        for (char c : s.toCharArray()) {
            if (c == '1') {
                initialOnes++;
            }
        }

        // L[i]: length of the block of same characters ending at i
        int[] L = new int[nt];
        L[0] = 1;
        for (int i = 1; i < nt; i++) {
            if (t.charAt(i) == t.charAt(i - 1)) {
                L[i] = L[i - 1] + 1;
            } else {
                L[i] = 1;
            }
        }

        // R[i]: length of the block of same characters starting at i
        int[] R = new int[nt];
        R[nt - 1] = 1;
        for (int i = nt - 2; i >= 0; i--) {
            if (t.charAt(i) == t.charAt(i + 1)) {
                R[i] = R[i + 1] + 1;
            } else {
                R[i] = 1;
            }
        }

        int maxGain = 0;
        // Iterate to find the start of each internal '1' block
        for (int i = 1; i < nt - 1; i++) {
            if (t.charAt(i) == '1' && t.charAt(i - 1) == '0') {
                int len1 = R[i];
                int j = i + len1 - 1; // end of the '1' block
                if (j + 1 < nt && t.charAt(j + 1) == '0') {
                    int len0_left = L[i - 1];
                    int len0_right = R[j + 1];
                    maxGain = Math.max(maxGain, len0_left + len0_right);
                }
            }
        }

        return initialOnes + maxGain;
    }
}
```
### Algorithm
*   **Core Idea:** Instead of creating an explicit list of blocks, we can use dynamic programming with prefix and suffix style calculations to find the lengths of blocks adjacent to any point in the string.
*   **Algorithm Steps:**
    1.  Construct the augmented string `t = '1' + s + '1'`. 
    2.  Calculate the initial number of '1's in `s`.
    3.  Create a `L` array of size `n+2`. `L[i]` will store the length of the contiguous block of identical characters ending at index `i`. This can be computed with a single pass from left to right.
    4.  Create a `R` array of size `n+2`. `R[i]` will store the length of the contiguous block of identical characters starting at index `i`. This is computed with a single pass from right to left.
    5.  Initialize `maxGain = 0`.
    6.  Iterate through the augmented string `t`. When we find the start of an internal '1' block (a '1' preceded by a '0'), we can determine its properties.
    7.  Let the '1' block start at index `i`. Its length is `R[i]`. The block ends at `j = i + R[i] - 1`.
    8.  If this '1' block is followed by a '0' (i.e., it's internal), the gain from this trade is the length of the '0' block to its left (`L[i-1]`) plus the length of the '0' block to its right (`R[j+1]`).
    9.  Update `maxGain` with the maximum such gain found.
    10. The final result is `initialOnes + maxGain`.

## Constant Space Sliding Window over Blocks
This is the most space-efficient approach. By recognizing that the calculation for a potential trade only depends on a local neighborhood of three blocks (`0-1-0`), we can avoid storing information about all blocks. We iterate through the string, identifying blocks on the fly. We maintain state for only the two most recently completed blocks. When we finish processing a new block, we have a window of three consecutive blocks, which is enough to determine if a valid trade is centered at the middle block and to calculate its gain. This avoids the O(N) space complexity of the previous approaches.
**Time:** O(N), as it requires a single pass through the string to identify all blocks. · **Space:** O(1) auxiliary space for the sliding window variables. The implementation shown uses O(N) to store the augmented string `t` for simplicity, but the algorithm itself can be implemented with true O(1) auxiliary space by handling boundary conditions of `s` directly.
**Pros:** Most space-efficient approach, using only a constant number of variables for the core logic.; Achieves optimal O(N) time complexity.
**Cons:** The logic for handling the augmented boundaries and iterating through blocks can be more complex to implement correctly compared to other approaches.; The provided code creates a temporary string `t` to simplify implementation, which technically uses O(N) space. A truly constant-space version would require more careful handling of string indices at the boundaries.
### Explanation
```java
class Solution {
    public int maximizeActiveSections(String s) {
        int n = s.length();
        int initialOnes = 0;
        for (char c : s.toCharArray()) {
            if (c == '1') {
                initialOnes++;
            }
        }

        // We build string t for simpler implementation. The core logic 
        // only needs constant extra variables.
        String t = "1" + s + "1";
        int nt = t.length();

        int maxGain = 0;
        int len_m2 = 0, len_m1 = 0;
        char type_m2 = ' ', type_m1 = ' '; // Initial empty/dummy blocks

        int ptr = 0;
        while (ptr < nt) {
            char type_curr = t.charAt(ptr);
            int start = ptr;
            while (ptr < nt && t.charAt(ptr) == type_curr) {
                ptr++;
            }
            int len_curr = ptr - start;

            // Check if the window of last 3 blocks is a 0-1-0 pattern
            if (type_m1 == '1' && type_m2 == '0' && type_curr == '0') {
                maxGain = Math.max(maxGain, len_m2 + len_curr);
            }
            
            // Slide the block window
            len_m2 = len_m1;
            type_m2 = type_m1;
            len_m1 = len_curr;
            type_m1 = type_curr;
        }

        return initialOnes + maxGain;
    }
}
```
### Algorithm
*   **Core Idea:** We can process the string in a single pass without storing all blocks or creating large auxiliary arrays. The idea is to use a sliding window of three blocks. As we scan the string, we only need to remember the information (type and length) of the last two blocks to evaluate the current block.
*   **Algorithm Steps:**
    1.  Calculate the initial number of '1's in `s`.
    2.  To simplify logic, we work on the augmented string `t = '1' + s + '1'`. 
    3.  Initialize variables to keep track of a sliding window of three blocks: `(type_m2, len_m2)` for the block two steps back, `(type_m1, len_m1)` for the previous block, and `(type_curr, len_curr)` for the current block.
    4.  Iterate through `t` with a pointer, identifying one block at a time.
    5.  After identifying `(type_curr, len_curr)`, check if the three-block window forms a `0-1-0` pattern. This happens if `type_m2 == '0'`, `type_m1 == '1'`, and `type_curr == '0'`. 
    6.  If it's a match, the potential gain is `len_m2 + len_curr`. Update `maxGain` with this value.
    7.  Slide the window: update `m2` with `m1`'s data and `m1` with `curr`'s data.
    8.  Continue until all blocks in `t` are processed.
    9.  Return `initialOnes + maxGain`.

# Solutions
### Java

```java
class Solution {
public
  int maxActiveSectionsAfterTrade(String s) {
    int n = s.length();
    int ans = 0, i = 0;
    int pre = Integer.MIN_VALUE, mx = 0;
    while (i < n) {
      int j = i + 1;
      while (j < n && s.charAt(j) == s.charAt(i)) {
        j++;
      }
      int cur = j - i;
      if (s.charAt(i) == '1') {
        ans += cur;
      } else {
        mx = Math.max(mx, pre + cur);
        pre = cur;
      }
      i = j;
    }
    ans += mx;
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxActiveSectionsAfterTrade(std ::string s) {
    int n = s.length();
    int ans = 0, i = 0;
    int pre = INT_MIN, mx = 0;
    while (i < n) {
      int j = i + 1;
      while (j < n && s[j] == s[i]) {
        j++;
      }
      int cur = j - i;
      if (s[i] == '1') {
        ans += cur;
      } else {
        mx = std ::max(mx, pre + cur);
        pre = cur;
      }
      i = j;
    }
    ans += mx;
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maxActiveSectionsAfterTrade(self, s: str) -> int: n = len(s) ans = i = 0 pre, mx = - inf, 0 while i < n: j = i + 1 while j < n and s[j] == s[i]: j += 1 cur = j - i if s[i] == "1": ans += cur else: mx = max(mx, pre + cur) pre = cur i = j ans += mx return ans

```