HardRating 2039

30. Substring with Concatenation of All Words

hash-tablestringsliding-window

解題說明

Substring with Concatenation of All Words

題目描述：給定字串 s 和一個由等長單詞組成的陣列 words，找出 s 中所有是 words 中所有單詞串接的子字串的起始索引。每個單詞必須恰好使用一次，但順序任意。

解題思路：每個單詞長度相同（設為 w），總窗口長度為 words.size() * w。對每個偏移 [0, w) 做滑動窗口：以 w 為步進移動右邊界，遇到合法單詞就加入窗口計數，超限時縮小左邊界，窗口恰好包含所有單詞時記錄起始索引。

C++ 解法

複雜度分析

時間複雜度：O(n × w) — 共 w 個偏移，每個偏移滑動窗口掃描 O(n) 個字元；每次子字串提取為 O(w)。

空間複雜度：O(m × w) — 雜湊表儲存 words 的頻率與當前窗口計數，最多 m 個條目，每條目長 w。

虛擬碼

1. Build frequency map `need` from words (word length = w)
2. For each offset off in [0, w):
   a. Init empty window map, left = off, count = 0
   b. For right = off to n-w in steps of w:
      - word = s[right..right+w)
      - If word in need:
        * window[word]++, count++
        * While window[word] > need[word]: shrink left by w, count--
        * If count == m: append left to result
      - Else: clear window, count = 0, left = right + w
3. Return result

其他解法

暴力法 O(n × m × w)：對每個起點切割成 m 個單詞並與 words 比對 — 正確但在 n 和 m 很大時過慢。

固定窗口哈希比對 O(n × m)：對每個起點建立完整窗口哈希表與 need 比對，不使用滑動；功能正確但無法共享相鄰窗口的計算結果。

延伸思考

若 words 中的單詞長度不等，解法如何根本性地改變？
按偏移分組的滑動窗口在 w 很大時與暴力法相比有何優勢？
若要求找出所有匹配的子字串本身（而非索引），如何在不額外複製字串的情況下回傳？

Substring with Concatenation of All Words — CaffeCode