3499. Maximize Active Section with Trade I

String
Greedy
Enumeration
Two Pointers

TIME

O(n)

SPACE

O(1)

Intuition

Augment to t = '1' + s + '1' and view it as alternating runs. A trade must pick a 1-run surrounded by 0s, i.e. an interior 1-run. Around it the runs look like:

... [0-run A] [1-run B] [0-run C] ...

Zeroing B fuses A, B, C into a single 0 block. That block is now bounded by 1s on both sides, so the second step converts all of it to 1s.

Accounting the change: we lose the B ones, then gain A + B + C ones. The B cancels, leaving:

net gain = A + C

So a trade is only ever worth the sum of the two zero-runs flanking the chosen 1-run, and the best trade is simply the largest sum of two adjacent zero-runs in t.

Approach

Build t = '1' + s + '1' (the sentinels guarantee every interior 1-run is genuinely surrounded by 0s, and that any merged 0 block has 1s on both sides).
Scan t collecting the lengths of its 0-runs in order. Consecutive entries in this list are, by construction, separated by exactly one 1-run.
The best gain is max(z[i] + z[i+1]) over adjacent pairs, or 0 if fewer than two zero-runs exist (no valid trade).
Return (number of '1' in s) + bestGain.

Complexity

Time: O(n), one scan to collect runs, one to compare adjacent pairs
Space: O(n), the list of zero-run lengths (O(1) achievable by tracking only the previous run)

Edge Cases

Fewer than two zero-runs → no valid trade → return the original count (Example 1)
All 1s → no zero-runs → gain 0
All 0s → one zero-run only → gain 0 (the single 1-run required in the middle doesn't exist)
The augmenting 1s are never counted in the answer, only '1's from s plus the gain
Adjacent zero-runs of length 1 each (e.g. "01010") still yield a gain of 2

Code

class Solution:
    def maxActiveSectionsAfterTrade(self, s: str) -> int:
        """
        3499. Maximize Active Section with Trade I
        Time: O(n)
        Space: O(1)
        """
        t = "1" + s + "1"
        base = s.count("1")

        best_gain = 0
        prev_zero = 0  # length of the previous 0-run
        i = 0
        n = len(t)
        while i < n:
            if t[i] == "0":
                j = i
                while j < n and t[j] == "0":
                    j += 1
                run = j - i
                if prev_zero:  # adjacent zero-runs -> a valid trade
                    best_gain = max(best_gain, prev_zero + run)
                prev_zero = run
                i = j
            else:
                i += 1

        return base + best_gain

/**
 * 3499. Maximize Active Section with Trade I
 * Time: O(n)
 * Space: O(1)
 */
class Solution {
    public int maxActiveSectionsAfterTrade(String s) {
        String t = "1" + s + "1";
        int base = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '1') {
                base++;
            }
        }

        int bestGain = 0;
        int prevZero = 0; // length of the previous 0-run
        int n = t.length();
        int i = 0;
        while (i < n) {
            if (t.charAt(i) == '0') {
                int j = i;
                while (j < n && t.charAt(j) == '0') {
                    j++;
                }
                int run = j - i;
                if (prevZero > 0) { // adjacent zero-runs -> a valid trade
                    bestGain = Math.max(bestGain, prevZero + run);
                }
                prevZero = run;
                i = j;
            } else {
                i++;
            }
        }

        return base + bestGain;
    }
}