演算法實作：最長無重複字元子字串 — 滑動視窗 + 雜湊表 O(n) 解法

題目

給定一個英文字串，找出第一個最長的不含重複字元的子字串。若有多個同長度，回傳最先出現者。

演算法：滑動視窗 + 字元位置雜湊表

維護一個「目前無重複視窗」[start, i]，掃描字串：

1. hash[256] 記錄每個 ASCII 字元最後出現的索引，初始 -1。
2. 掃描到字元 s[i]：
   • 若 hash[s[i]] < start：字元不在當前視窗內 → 視窗擴大，更新 hash[s[i]] = i。
   • 否則：字元在視窗內重複 → 視窗起點跳至 hash[s[i]] + 1，更新 hash，並檢查前一視窗長度是否為最大。
3. 掃描結束後，檢查尾端視窗長度。

修正版完整 C++ 程式碼

#include 
#include 

char* GetSubStr(const char* str) {
    int hash[256];
    for (int i = 0; i < 256; i++) hash[i] = -1;
    
    int start = 0, maxStart = 0, maxEnd = 0;
    int strLen = strlen(str);
    
    for (int i = 0; i < strLen; i++) {
        unsigned char c = str[i];  // 避免負索引
        if (hash[c] < start) {
            hash[c] = i;  // 字元不在當前視窗，擴大視窗
        } else {
            // 字元在視窗內重複
            int curLen = i - start;
            if (curLen > maxEnd - maxStart) {
                maxStart = start;
                maxEnd = i;
            }
            start = hash[c] + 1;  // 視窗起點跳過重複字元
            hash[c] = i;
        }
    }
    
    // 處理字串結尾的視窗
    if (strLen - start > maxEnd - maxStart) {
        maxStart = start;
        maxEnd = strLen;
    }
    
    int maxLen = maxEnd - maxStart;
    char* result = (char*)malloc(maxLen + 1);
    memcpy(result, str + maxStart, maxLen);
    result[maxLen] = '\0';
    return result;
}

關鍵修正點

複雜度分析

• 時間：O(n) — 每字元最多進出視窗一次。
• 空間：O(1) — 固定 256 整數陣列 (ASCII)，Unicode 擴充用雜湊表 O(min(n, |Σ|))。

測試案例

"abcabcbb"  → "abc"     (長度 3)
"bbbbb"     → "b"       (長度 1)
"pwwkew"    → "wke"     (長度 3)
" "         → " "       (空白字元)
"dvdf"      → "vdf"     (長度 3, 非 "dvd")

C 版本 (不動態配置記憶體)

void GetSubStrInPlace(const char* str, char* out, int* outLen) {
    int hash[256]; /* ... 同邏輯 ... */
    /* 直接寫入 out 緩衝區，回傳長度 */
}

核心洞見：「字元最後出現位置」是連結過去與未來的關鍵資訊。滑動視窗不需嵌套迴圈，單趟掃描即可維護無重複區間，是處理「子字串/子陣列滿足特定條件」問題的通用模板。