# LeetCode 3499: Maximise Active Section with Trade

You're given a binary string where `1` represents an active section and `0` represents an inactive one. You get exactly one trade:

1.  Erase a block of `1`s that has `0`s on both sides.
    
2.  Fill a block of `0`s that has `1`s on both sides.
    

The goal is to maximise the final number of active sections.

At first glance, the problem encourages you to think about flipping individual bits. That quickly becomes messy. The trick is to change the unit of thinking and instead look at **runs** of consecutive `1`s and `0`s.

![](https://cdn.hashnode.com/uploads/covers/61cdeb06b9f0453f6d320704/bc5d7a54-45cd-4b51-8ecd-8ce76bc7c4b7.png align="center")

The first solution explicitly uses **Run Length Encoding (RLE)** to represent those runs. The second builds on the same idea but processes the runs as they are encountered, reducing the extra space to **O(1)**.

The problem also pads the string as:

```cpp
t = "1" + s + "1";
```

This handles the boundaries for free. Any `1` block touching either end of the original string becomes connected to the padded `1`, so it only has a `0` on one side and can never be erased. Every remaining `1` run is therefore a valid candidate.

![](https://cdn.hashnode.com/uploads/covers/61cdeb06b9f0453f6d320704/15f52566-cd3e-4409-ae8a-0e509a5d0b78.png align="center")

### Observation

Suppose we erase a valid `1` block.

The zero runs on its left and right immediately merge into a larger zero run. Since that merged run is now surrounded by `1`s, it becomes exactly the block we fill in the second step.

Although the erased block briefly becomes `0`, it is immediately restored to `1` when the merged zero run is filled, so its contribution never changes.

The only real gain comes from converting the two neighbouring zero runs into `1`s.

![](https://cdn.hashnode.com/uploads/covers/61cdeb06b9f0453f6d320704/51365377-ede4-4985-9c97-93c820234712.png align="center")

That means every candidate block has a score of:

```text
totalOnes + leftZeroRun + rightZeroRun
```

So the answer is simply:

```text
answer = totalOnes + max(leftZeroRun + rightZeroRun)
```

![](https://cdn.hashnode.com/uploads/covers/61cdeb06b9f0453f6d320704/c45e2772-9449-48e2-a1ed-7ed1f2caaabd.png align="center")

taken over every valid `1` block.

If no valid block exists, the answer is simply `totalOnes`.

### O(n) Time, O(n) Space Solution

```cpp
class Solution {
public:
    int maxActiveSectionsAfterTrade(string s) {

        string t = "1" + s + "1";

        vector<pair<char,int>> runs;

        for (int i = 0; i < t.size();) {

            int j = i;

            while (j < t.size() && t[j] == t[i])
                j++;

            runs.push_back({t[i], j - i});

            i = j;
        }

        int totalOnes = count(s.begin(), s.end(), '1');

        int maxGain = 0;

        for (int i = 1; i + 1 < runs.size(); i++) {

            if (runs[i].first == '1') {

                maxGain = max(maxGain,
                              runs[i - 1].second +
                              runs[i + 1].second);
            }
        }

        return totalOnes + maxGain;
    }
};
```

This solution explicitly builds the Run Length Encoding by storing every run as a `(character, length)` pair.

![](https://cdn.hashnode.com/uploads/covers/61cdeb06b9f0453f6d320704/8d78cd1b-6aef-42d1-8f80-502378ae06d4.png align="center")

Since the first and last runs always contain the padded `1`s, scanning from `1` to `runs.size() - 2` automatically skips the boundary cases.

Every remaining `1` run already has a zero run on both sides, so scoring it is simply a matter of adding the lengths of its neighbouring zero runs.

Building the runs and scanning them both take linear time.

**Complexity:**

*   Time Complexity: `O(n)`
    
*   Space Complexity: `O(n)`
    

### O(n) Time, O(1) Space Solution

The previous solution only needs the current run and its immediate neighbours, so storing every run is unnecessary.

![](https://cdn.hashnode.com/uploads/covers/61cdeb06b9f0453f6d320704/9fb86b92-deba-4d8d-bae0-34d0033dd7f8.png align="center")

Instead, process the string one run at a time.

Every zero run is the right neighbour of one `1` block and the left neighbour of the next, so once a zero run ends we already have everything needed to score the previous block.

```cpp
class Solution {
public:
    int maxActiveSectionsAfterTrade(string s) {

        int totalOnes = 0;

        int prevZero = 0;
        int curZeros = 0;

        bool havePending = false;

        int maxGain = 0;

        for (int i = 0; i < s.size(); i++) {

            if (s[i] == '1') {

                totalOnes++;

                if (i == 0 || s[i - 1] == '0') {

                    if (i > 0) {

                        if (havePending) {

                            maxGain = max(maxGain,
                                          prevZero + curZeros);
                        }

                        prevZero = curZeros;
                        havePending = true;

                    } else {

                        havePending = false;
                    }

                    curZeros = 0;
                }

            } else {

                curZeros++;
            }
        }

        if (!s.empty() && s.back() == '0' && havePending) {

            maxGain = max(maxGain,
                          prevZero + curZeros);
        }

        return totalOnes + maxGain;
    }
};
```

`curZeros` tracks the zero run currently being traversed.

When a new `1` block begins, that zero run has just ended, which means we now know the right neighbour of the previous block.

After scoring it, that same zero run immediately becomes the left neighbour of the next block.

If the string ends with `0`s, the final pending block never gets scored inside the loop, so we handle that single case after the scan finishes.

**Complexity:**

*   Time Complexity: `O(n)`
    
*   Space Complexity: `O(1)`
    

### Edge Cases

One subtle detail is easy to miss.

The problem lets us erase one block and fill another, but it never says those two blocks have to be related.

Could erasing one block and filling a completely different zero run ever produce a better answer?

No.

If a zero run can already be filled independently, then it was already surrounded by `1`s.

Filling it gains its length, but the erased block is permanently lost, so the net gain is:

```text
size(zero run) - size(erased block)
```

Now erase one of that zero run's neighbouring `1` blocks instead.

The erased block is rebuilt as part of the fill operation, and you gain the original zero run plus the zero run on the other side.

That is always at least as good because nothing is permanently lost.

The only exception is when the string has exactly three runs:

```text
111...000...111
```

Both `1` blocks touch the boundary, so neither can be erased.

There is no valid trade, which means the answer is simply the original number of `1`s.

### Conclusion

The key to this problem is changing how you look at the string.

Once you stop thinking about individual characters and start thinking in terms of runs, the trade becomes easy to score.

From there, the explicit Run Length Encoding solution is straightforward, and the `O(1)` solution naturally follows by processing those same runs on the fly.