單次遍歷解決：英文字串中首個最長不重複子串的高效演算法

問題描述

給定一個僅包含英文字元的字串，找出其中第一個出現的最長不含重複字元的子串。要求時間複雜度 O(n)，空間複雜度 O(1)（固定 256 字元集）。

核心思路：滑動窗口 + 字元位置哈希表

• 維護一個「當前無重複窗口」[CurrentStart, i]。
• 用 hash[256] 記錄每個字元最近一次出現的索引，初始為 -1。
• 遍歷字串，對於字元 str[i]：
  • 若 hash[str[i]] < CurrentStart，說明該字元在當前窗口未出現 → 擴展窗口，更新 hash[str[i]] = i。
  • 否則（重複）：
    • 計算當前窗口長度 CurrentLength = i - CurrentStart，若大於歷史最大長度，更新 MaxStart、MaxEnd。
    • 將窗口起點跳至重複字元上一次位置的下一個：CurrentStart = hash[str[i]] + 1。
    • 更新 hash[str[i]] = i。
• 遍歷結束後，需補檢查最後一個窗口是否為最長。

完整實作（C 風格，動態分配記憶體）

char* GetMaxSubStr(char* str) {
    int hash[256];
    for (int i = 0; i < 256; ++i) hash[i] = -1;

    int CurrentStart = 0, MaxStart = 0, MaxEnd = 0;
    int strLen = strlen(str);

    for (int i = 0; i < strLen; ++i) {
        if (CurrentStart > hash[str[i]]) {
            hash[str[i]] = i;                 // 無重複，擴展窗口
        } else {
            int CurrentLength = i - CurrentStart;
            if (CurrentLength > MaxEnd - MaxStart) {
                MaxEnd = i;
                MaxStart = CurrentStart;
            }
            CurrentStart = hash[str[i]] + 1;  // 縮減窗口，跳過重複字元
            hash[str[i]] = i;
        }
    }

    // 處理遍歷結束後最後一個窗口
    if (strLen - CurrentStart > MaxEnd - MaxStart) {
        MaxEnd = strLen;
        MaxStart = CurrentStart;
    }

    int MaxLength = MaxEnd - MaxStart;
    char* reStr = (char*)malloc(MaxLength + 1);
    reStr[MaxLength] = '\0';
    memcpy(reStr, str + MaxStart, MaxLength);
    return reStr;  // 呼叫端需 free()
}

關鍵細節說明

1. 初始化 hash 為 -1：表示字元尚未出現，配合 CurrentStart 初始為 0，首次遇到任意字元時 CurrentStart (0) > hash[c] (-1) 成立，正確判定為「無重複」。
2. 窗口縮減邏輯：CurrentStart = hash[str[i]] + 1 確保新窗口不包含重複字元，且保留盡可能長的尾部。
3. 最終補檢查：迴圈結束時，最後一個窗口可能未觸發重複分支，必須額外比較一次。
4. 記憶體管理：函式回傳 malloc 分配的記憶體，使用者必須 free()；若不想動態分配，可改為填充呼叫端提供的緩衝區。

複雜度分析

• 時間：O(n)，單次遍歷，每字元常數時間操作。
• 空間：O(1)，固定 256 int 陣列 + 少量變數。

適用範圍與限制

• ✅ 適用於 ASCII / 延伸 ASCII（256 字元集）字串。
• ❌ 不直接支援 Unicode（需改用哈希表或位圖，空間不再 O(1)）。
• ❌ 僅回傳「第一個」最長子串；若需所有最長子串，需修改記錄邏輯。

修正版補充（針對原文提到的 Bug 修復）

原文作者後續發現原版在處理字串尾部無重複情況有誤，補充了迴圈後的檢查邏輯（見上方完整實作）。這正是「測試驅動開發」的典型案例：沒有測試用例保證的程式碼只是無序字元。