3499. Maximize Active Section with Trade I

題目 / Problem

中文 給你一個長度為 n 的二進位字串 s：'1' 代表一個「啟用 (active)」區段，'0' 代表「未啟用 (inactive)」區段。你最多可以做 一次交易 (trade)，一次交易包含兩個步驟：

1. 選一段被 '0' 左右包夾的連續 '1'，把它們全部變成 '0'。
2. 接著選一段被 '1' 左右包夾的連續 '0'，把它們全部變成 '1'。

回傳做完最佳交易後，s 裡 '1' 的最大數量。注意：把 s 想像成頭尾各補一個 '1'，即 t = '1' + s + '1'，但這兩個補上的 '1' 不計入最後答案。

English You are given a binary string s of length n, where '1' is an active section and '0' is inactive. You may perform at most one trade, which has two steps:

1. Pick a contiguous block of '1's that is surrounded by '0's on both sides, and turn it all into '0's.
2. Then pick a contiguous block of '0's that is surrounded by '1's on both sides, and turn it all into '1's.

Return the maximum number of '1's after the optimal trade. Treat s as if augmented to t = '1' + s + '1'; those two extra '1's do not count in the final answer.

Constraints - 1 <= n == s.length <= 10^5 - s[i] is either '0' or '1'

Worked example s = "0100" → Output 4. Augment to "101001", turn the middle 1 into 0 ("100001"), then fill the surrounded 0000 with 1s ("111111"). Removing the two augmented ends gives "1111" → four active sections.

名詞解釋 / Glossary

• 二進位字串 / binary string：只由 '0' 和 '1' 組成的字串 / a string made only of the characters '0' and '1'.
• 連續區段 (run/segment) / run：一段相同字元連在一起的最長子串，例如 "1000100" 可切成 1 | 000 | 1 | 00。/ a maximal stretch of identical characters, e.g. "1000100" splits into 1 | 000 | 1 | 00.
• 包夾 (surrounded) / surrounded：某個區段的「左邊緊鄰」與「右邊緊鄰」都是另一種字元。/ a segment whose immediate left neighbor and immediate right neighbor are both the other character.
• delta（增量）/ delta：做一次交易能「多賺到」的 '1' 數量。答案 = 原本 '1' 的總數 + 最大 delta。/ the extra number of '1's a single trade can gain; answer = total ones + max delta.
• 枚舉 (enumeration) / enumeration：把所有候選情況一個一個列出來比較，取最好的。/ trying every candidate one by one and keeping the best.
• 指標解引用 *p / pointer dereference（C）：char* s 是指向字元的指標，s[i] 讀取第 i 個字元。/ char* s points at characters; s[i] reads the i-th one.
• malloc / free（C）：向系統要一塊記憶體、用完歸還，避免記憶體洩漏。/ request a block of memory and release it when done, avoiding leaks.

思路

先想最暴力的做法：把每一種合法交易都真的模擬一遍，改字串、數 '1'，取最大值。但字串長達 10^5，每次模擬又是 O(n)，交易種類也是 O(n)，總共 O(n^2)，會超時，所以要找規律。關鍵觀察是：'1' 的總數 totalOnes 是固定的基底，我們只需要算出「一次交易最多能額外增加多少個 '1'」，也就是最大 delta。把 s 切成交替的區段（例如 0 | 1 | 00），一次合法交易一定是挑一段「左右都被 '0' 包住的 '1' 區段」。把這段 '1' 變成 '0' 後，它左右兩個 '0' 區段就會合併成一大塊、且被 '1' 包住，於是可以整塊填成 '1'。算一下收支：這段 '1' 先變 0 再變回 1（不賺不賠），真正新增的是左邊那段 '0' 和右邊那段 '0' 全變成了 '1'。所以 delta 就等於「左鄰 '0' 區段長度 + 右鄰 '0' 區段長度」。因此只要掃一遍字串、切出所有區段，對每個「兩側都是 '0'」的 '1' 區段算 左長+右長，取最大當作 delta，答案就是 totalOnes + maxDelta。頭尾的 '1' 區段（貼著字串邊界）因為只有一側有 '0'，不算合法候選，這正對應題目「補頭尾 '1'」的說明。

Start from brute force: actually simulate every legal trade, rewrite the string, recount '1's, and take the max. With n up to 10^5 that is O(n^2) and times out, so we look for structure. The number of '1's, totalOnes, is a fixed base — we only need the biggest extra gain a single trade can add (the max delta). Break s into alternating runs (e.g. 0 | 1 | 00). Any legal trade must pick a '1'-run that has a '0'-run on both sides. Zeroing that '1'-run merges its two neighboring '0'-runs into one block that is now surrounded by '1's, so we can fill the whole block with '1's. Accounting: the '1'-run goes 1 → 0 → 1 (break-even), and the real gain is that the left '0'-run and the right '0'-run all became '1'. Hence delta = len(left zero run) + len(right zero run). So we scan once, split into runs, and for every '1'-run flanked by zeros on both sides compute left + right; the largest such value is the max delta, and the answer is totalOnes + maxDelta. A '1'-run touching the string boundary has a zero on only one side, so it is not a valid candidate — exactly what the "augment with '1' at both ends" note describes.

逐步走查 / Walkthrough

Input: s = "0100".

Step A — count ones / 先數 '1': totalOnes = 1.

Step B — split into runs / 切成區段:

Step C — scan interior runs (k from 1 to m-2) / 掃描中間的區段:

Step D — answer / 算答案: totalOnes + best = 1 + 3 = 4. ✅

Solution — C

#include <string.h>   // strlen
#include <stdlib.h>   // malloc, free

/*
 * 演算法 / Algorithm:
 * 1) 統計 '1' 的總數作為基底 / count all '1's as the base.
 * 2) 把字串切成交替區段；對每個「左右都是 '0'」的 '1' 區段，
 *    delta = 左 '0' 長 + 右 '0' 長 / for each '1'-run flanked by zeros, delta = left0 + right0.
 * 3) 答案 = 基底 + 最大 delta / answer = base + max delta.
 */
int maxActiveSectionsAfterTrade(char* s) {
    int n = (int)strlen(s);            // n 是字串長度 / n is the string length

    int totalOnes = 0;                 // 目前的 '1' 總數（固定基底）/ base count of ones
    for (int i = 0; i < n; i++)        // 逐字掃描 / scan character by character
        if (s[i] == '1')               // s[i] 取第 i 個字元 / s[i] reads the i-th char
            totalOnes++;               // 遇到 '1' 就加一 / one more active section

    // runLen[k] / runCh[k]：第 k 個區段的長度與字元 / length & char of the k-th run.
    // 最多 n 個區段，所以配置 n 格 / at most n runs, so allocate n slots.
    int  *runLen = (int*)malloc(sizeof(int)  * (n > 0 ? n : 1)); // malloc 向系統要記憶體 / request memory
    char *runCh  = (char*)malloc(sizeof(char) * (n > 0 ? n : 1));
    int m = 0;                         // m 是已切出的區段數 / number of runs found so far

    int i = 0;                         // i 指向目前區段的起點 / start of the current run
    while (i < n) {                    // 掃完整個字串 / until we consume the whole string
        int j = i;                     // j 往右找相同字元的結尾 / j scans right while same char
        while (j < n && s[j] == s[i])  // 只要字元和起點一樣就前進 / advance while char matches
            j++;
        runCh[m]  = s[i];              // 這個區段的字元 / this run's character
        runLen[m] = j - i;             // 這個區段的長度 / this run's length
        m++;                           // 記錄一個新區段 / one more run recorded
        i = j;                         // 跳到下一個區段起點 / jump to next run's start
    }

    int best = 0;                      // 最大 delta，預設 0（不交易）/ max delta, default 0 (no trade)
    // 只看「中間」的區段：k 從 1 到 m-2，保證左右鄰居都存在
    // only interior runs (k in [1, m-2]) so both neighbors exist
    for (int k = 1; k + 1 < m; k++) {
        // 中間的 '1' 區段，其左右一定是 '0'（區段交替），仍明確檢查以求清楚
        // a '1'-run flanked by '0'-runs; runs alternate, but we check explicitly for clarity
        if (runCh[k] == '1' && runCh[k - 1] == '0' && runCh[k + 1] == '0') {
            int delta = runLen[k - 1] + runLen[k + 1]; // 左 '0' 長 + 右 '0' 長 / left0 + right0
            if (delta > best)          // 保留最大值 / keep the maximum
                best = delta;
        }
    }

    free(runLen);                      // 歸還記憶體，避免洩漏 / release memory to avoid a leak
    free(runCh);
    return totalOnes + best;           // 基底 + 最佳增量 / base + best delta
}

Solution — C++

#include <string>
#include <vector>
#include <utility>     // std::pair
#include <algorithm>   // std::count, std::max
using namespace std;

/*
 * 演算法 / Algorithm: 與 C 版相同 / same as the C version —
 * 統計 '1' 總數，切成交替區段，對每個被 '0' 包夾的 '1' 區段取
 * (左 '0' 長 + 右 '0' 長) 的最大值當 delta，答案 = 總數 + delta。
 * Count ones, split into runs, and for each '1'-run surrounded by '0'-runs
 * take max(left0 + right0) as delta; answer = totalOnes + delta.
 */
class Solution {
public:
    int maxActiveSectionsAfterTrade(string s) {
        int n = (int)s.size();                       // 字串長度 / string length

        // count 是 STL 演算法，數出區間內等於 '1' 的個數 / std::count tallies '1's in the range
        int totalOnes = (int)count(s.begin(), s.end(), '1');

        // runs：每個元素是 {字元, 長度} 的 pair / each element is a {char, length} pair.
        // vector 是可自動增長的陣列 / vector is a dynamic (auto-growing) array.
        vector<pair<char, int>> runs;
        for (int i = 0; i < n; ) {                   // 外層不自增，內層跳到下一區段 / i jumps run by run
            int j = i;                               // j 找相同字元的結尾 / extend while char is equal
            while (j < n && s[j] == s[i]) j++;
            runs.push_back({s[i], j - i});           // 記錄 {字元, 長度} / store {char, length}
            i = j;                                   // 前進到下一區段 / move to next run
        }

        int best = 0;                                // 最大 delta / max delta (0 = no trade)
        // k 從 1 到 size-2，確保 runs[k-1] 與 runs[k+1] 都存在
        // k in [1, size-2] so both neighbors exist
        for (int k = 1; k + 1 < (int)runs.size(); k++) {
            // 中間被 '0' 包夾的 '1' 區段 / a '1'-run surrounded by '0'-runs
            if (runs[k].first == '1' &&
                runs[k - 1].first == '0' &&
                runs[k + 1].first == '0') {
                // .second 取 pair 的第二個值（長度）/ .second is the pair's length field
                best = max(best, runs[k - 1].second + runs[k + 1].second);
            }
        }

        return totalOnes + best;                     // 基底 + 最佳增量 / base + best delta
    }
};

複雜度 / Complexity

• Time: O(n) — 我們只掃字串常數次（數 '1'、切區段、掃區段），每次都是線性；n 是字串長度。/ We pass over the string a constant number of times (count ones, build runs, scan runs); each pass is linear in n, the string length.
• Space: O(n) — 儲存區段的陣列 / vector，最壞情況（如 "0101..."）有 O(n) 個區段。/ The run arrays / vector can hold up to O(n) runs in the worst case (e.g. "0101...").

Pitfalls & Edge Cases

• 邊界的 '1' 區段不算 / boundary '1'-runs are not candidates：貼著字串頭或尾的 '1' 只有一側有 '0'，不是合法交易。程式用 k 從 1 到 m-2 自然排除，等同題目「頭尾補 '1'」的規則。/ A '1'-run touching either end has a zero on only one side, so it is illegal; looping k from 1 to m-2 skips it, matching the "augment with '1'" rule.
• 沒有合法交易時 / when no trade is possible：例如 "01" 或全 '1'，best 保持 0，答案就是原本的 totalOnes。因為題目說「最多一次」，不交易也允許。/ For inputs like "01" or all-ones, best stays 0 and the answer is just totalOnes — "at most one" allows doing nothing.
• 別真的去改字串模擬 / don't literally simulate the rewrite：O(n^2) 會超時；把收支化簡成 delta = 左0長 + 右0長 才是重點。/ Simulating each trade is O(n^2) and times out; the insight is delta = left0 + right0.
• 記憶體管理（C）/ memory management (C)：malloc 拿到的記憶體最後要 free，否則洩漏。/ Every malloc must be paired with free or you leak memory.
• 答案不會溢位 / no overflow：n <= 10^5，int 綽綽有餘，不需要 long long。/ With n <= 10^5, an int easily holds the result; long long is unnecessary.