3090. Maximum Length Substring With Two Occurrences

題目 / Problem

中文： 給定一個字串 s，請回傳一個子字串的最大長度，這個子字串中每個字元最多出現兩次。

English: Given a string s, return the maximum length of a substring such that each character appears at most twice inside it.

約束 / Constraints: - 2 <= s.length <= 100 - s 只由小寫英文字母組成 / s consists only of lowercase English letters.

範例 / Example: - Input: s = "bcbbbcba" - Output: 4 - 說明 / Explanation: 子字串 "bcba"（原字串最後四個字元）長度為 4，其中 b 出現 2 次、c 出現 1 次、a 出現 1 次，都不超過兩次。沒有更長的合法子字串了。/ The substring "bcba" (the last four characters) has length 4; b appears twice, c and a once each — none exceeds twice. No longer valid substring exists.

名詞解釋 / Glossary

• 子字串 / Substring: 字串中連續的一段字元。例如 "bcbbbcba" 的 "bcb" 是子字串，但 "bcb...a" 中跳著取的字元不算。/ A contiguous run of characters inside the string. Contiguity is what makes this different from a subsequence.
• 滑動視窗 / Sliding window: 用兩個指標 left 和 right 框出一段連續區間，隨著掃描不斷向右移動、伸縮這個區間的技巧。/ A technique using two indices left and right to bound a contiguous range that grows and shrinks as you scan, so you never re-examine the whole string from scratch.
• 雙指針 / Two pointers: 兩個一起移動的索引變數；這裡就是視窗的左右邊界。/ Two index variables that move together — here they are the window's boundaries.
• 計數陣列 / Count array: 一個大小固定的陣列，用索引代表字元、值代表出現次數。因為只有 26 個小寫字母，用 cnt[26] 就夠了。/ A fixed-size array where the index represents a character and the value stores how many times it currently appears. Since there are only 26 lowercase letters, cnt[26] suffices — it acts like a tiny hash table.
• 不變量 / Invariant: 在演算法每一步都保持為真的條件。這裡的不變量是「視窗內每個字元出現次數 ≤ 2」。/ A condition that stays true at every step of the algorithm. Here: "every character inside the window appears at most twice."

思路

最直接的想法是暴力法：枚舉所有可能的子字串（選一個起點、一個終點），對每個子字串數一遍每種字元的出現次數，若全部都 ≤ 2 就更新答案。因為 s.length 最多只有 100，這種 O(n³) 或 O(n²·26) 的做法其實完全能過。但它做了很多重複工作——每次都從頭數起。我們可以更聰明。

更好的做法是滑動視窗。我們維持一個區間 [left, right]，並保持一個不變量：視窗裡每個字元最多出現兩次。用一個 cnt[26] 陣列記錄視窗內每個字母的出現次數。我們讓 right 從左到右一格一格擴張，每次把 s[right] 加入視窗（對應的計數加一）。加入之後，如果這個字元的計數變成 3，就代表不變量被破壞了——這時我們從左邊縮小視窗：不斷把 s[left] 移出（計數減一）並讓 left 右移，直到那個超標的字元計數降回 2 為止。每當視窗合法時，用當前視窗長度 right - left + 1 更新答案。因為每個字元最多被 right 加入一次、被 left 移出一次，總共只掃兩遍，所以是 O(n)。關鍵在於：一旦某字元超過兩次，唯一能修復的方法就是丟掉左邊那個多出來的同字元，而 left 只會往右走、不會倒退，這保證了效率也保證了正確性。

The most direct idea is brute force: enumerate every substring (pick a start and an end), count each character's occurrences, and if all are ≤ 2, update the answer. Since s.length is at most 100, this O(n³) approach easily passes. But it repeats a lot of work by recounting from scratch every time. We can do better.

The cleaner approach is a sliding window. We keep a range [left, right] and maintain the invariant that every character inside appears at most twice, tracking counts in a cnt[26] array. We expand right one step at a time, adding s[right] to the window (incrementing its count). If that count hits 3, the invariant is broken, so we shrink from the left: repeatedly remove s[left] (decrement) and advance left until the offending character drops back to 2. Whenever the window is valid, we update the answer with the current length right - left + 1. Each character is added once by right and removed at most once by left, so the whole thing is two passes — O(n). The key insight: the only way to fix an over-count is to discard the extra copy on the left, and since left never moves backward, both correctness and efficiency are guaranteed.

逐步走查 / Walkthrough

輸入 / Input: s = "bcbbbcba"（索引 0..7）。我們追蹤 left、right、計數陣列，以及答案 ans。

最終答案 / Final answer: 4（子字串 "bcba"）。

Solution — C

// 演算法：滑動視窗 + 26 大小計數陣列。right 擴張，若某字元計數超過 2 就從左縮小，
// 每個合法視窗更新最大長度。時間 O(n)，空間 O(1)。
// Algorithm: sliding window with a 26-slot count array. Expand right; if any char
// exceeds 2, shrink from left; update the max valid window length. O(n) time, O(1) space.
int maximumLengthSubstring(char* s) {
    int cnt[26] = {0};          // 每個字母在視窗內的出現次數，初值全 0 / occurrences of each letter in the window, all zero
    int left = 0;               // 視窗左邊界 / left boundary of the window
    int ans = 0;                // 目前找到的最大合法長度 / best valid length so far

    // right 逐一掃過整個字串，作為視窗右邊界 / right scans the whole string as the window's right edge
    for (int right = 0; s[right] != ''; right++) {
        int c = s[right] - 'a';   // 把字元轉成 0..25 的索引（'a'→0, 'b'→1 …）/ map char to index 0..25
        cnt[c]++;                 // 新字元加入視窗，次數加一 / new char enters the window, bump its count

        // 若這個字元出現超過兩次，不斷從左移出直到修復不變量
        // While this char appears more than twice, drop chars from the left until fixed
        while (cnt[c] > 2) {
            cnt[s[left] - 'a']--; // 把最左字元移出視窗，其次數減一 / remove leftmost char, decrement its count
            left++;               // 左邊界右移一格 / advance the left boundary
        }

        // 現在視窗 [left, right] 合法，用它的長度更新答案
        // Window [left, right] is now valid; update answer with its length
        int len = right - left + 1;  // 視窗長度 / current window length
        if (len > ans) ans = len;    // 取較大者 / keep the larger
    }
    return ans;   // 回傳最大長度 / return the maximum length
}

Solution — C++

// 演算法同 C 版：滑動視窗維持「每字元 ≤ 2 次」的不變量，用 array<int,26> 計數。
// 時間 O(n)，空間 O(1)。
// Same as the C version: a sliding window keeping the "each char ≤ 2" invariant,
// counting with array<int,26>. O(n) time, O(1) space.
class Solution {
public:
    int maximumLengthSubstring(string s) {
        array<int, 26> cnt{};     // 固定 26 格計數陣列，{} 使全部初始化為 0 / fixed 26-slot counts, {} zero-inits all
        int left = 0;             // 視窗左邊界 / left boundary
        int ans = 0;              // 目前最大合法長度 / best valid length so far

        // 用範圍 for 需要索引，這裡改用傳統 for 以便同時存取 left/right
        // We need indices for both ends, so use a classic indexed for-loop
        for (int right = 0; right < (int)s.size(); ++right) {
            int c = s[right] - 'a';   // 字元轉 0..25 索引 / char to index 0..25
            ++cnt[c];                 // 加入視窗，計數加一 / add to window, increment count

            // 出現超過兩次就從左縮小視窗 / shrink from the left while it appears >2 times
            while (cnt[c] > 2) {
                --cnt[s[left] - 'a'];  // 移出最左字元 / drop the leftmost char's count
                ++left;                // 左邊界右移 / move left boundary right
            }

            // max() 取當前視窗長度與舊答案的較大值 / max() keeps the larger of window length and old answer
            ans = max(ans, right - left + 1);
        }
        return ans;   // 回傳結果 / return the result
    }
};

複雜度 / Complexity

• Time: O(n) — n 是字串長度。right 從頭掃到尾一次；left 只會往右移動、且移動總次數不超過 n。雖然有內層 while，但每個字元最多被移出一次，所以兩個指標合計移動 O(n) 步，不是 O(n²)。/ n is the string length. right traverses once; left only moves right, at most n times total. The inner while doesn't make it quadratic because each character is removed at most once.
• Space: O(1) — 只用一個固定 26 格的計數陣列，與輸入長度無關。/ Only a fixed 26-slot count array, independent of input length.

Pitfalls & Edge Cases

• 視窗長度計算的差一錯誤 / Off-by-one in window length: 長度是 right - left + 1 而非 right - left，因為兩端都包含在內。少了 +1 會讓答案全部小 1。/ The length is right - left + 1, not right - left, because both ends are inclusive; forgetting +1 undercounts by one everywhere.
• 用 if 而不是 while 縮小視窗 / Using if instead of while to shrink: 一般情況下每步只需移出一個字元，但為了保持不變量的通用寫法，應該用 while 直到計數 ≤ 2。這裡雖然單次 if 也剛好夠（每次只加一個字元），但 while 更穩健、意圖更清楚。/ One removal usually suffices, but while is the robust, general form that guarantees the invariant; it reads more clearly as "shrink until valid."
• 忘記在移出時同步遞減計數 / Forgetting to decrement on removal: 縮小視窗時必須對 s[left] 對應的計數減一，否則計數會失真、視窗永遠「卡住」。程式碼在 left++ 之前先做 cnt[...]--。/ When shrinking, you must decrement the count for s[left], or counts drift and the window never recovers; the code decrements before advancing left.
• 字元轉索引 / Char-to-index conversion: s[i] - 'a' 依賴輸入全為小寫字母（約束已保證）。若含大寫或其他字元，索引會越界。/ s[i] - 'a' relies on all-lowercase input (guaranteed by constraints); other characters would produce out-of-range indices.
• 最短輸入 / Minimum input: n = 2 時（如 "aa"）答案是 2，"ab" 也是 2；滑動視窗自然處理，無需特判。/ With n = 2 (e.g. "aa" → 2, "ab" → 2), the window handles it naturally with no special case.