LeetCode 經典題目：Substring with Concatenation of All Words 滑動窗口 O(N) 解法深度解析

問題描述

給定字串 s 與等長單字陣列 words，找出 s 中所有由 words 全排列拼接形成的子串起始索引。單字間無間隔字符，順序不限。

範例

s = "barfoothefoobarman"
words = ["foo", "bar"]
輸出: [0, 9]
解釋: 
索引 0: "barfoo" = "bar" + "foo"
索引 9: "foobar" = "foo" + "bar"

核心演算法：多輪滑動窗口 + 雙 HashMap

關鍵參數定義

• wordLen：單字長度（所有單字等長）
• numWord：單字總數
• windowLen = wordLen * numWord：窗口總長度
• sLen：字串 s 長度

演算法邏輯

1. 外層循環：遍歷 0 ~ wordLen-1 作為窗口起始偏移，覆蓋所有可能對齊位置
2. 內層滑動：步長為 wordLen，維護固定大小窗口
3. 雙 Map 統計：
   • targetMap：words 頻率統計（固定）
   • windowMap：當前窗口單字頻率（動態更新）
4. 計數器優化：count 記錄超額單字數，count==0 表示窗口有效
5. 增量更新：窗口滑動時只需移除舊單字、加入新單字，O(1) 更新

完整 Java 實作

public class Solution {
    public List findSubstring(String s, String[] words) {
        List res = new ArrayList<>();
        if (words == null || words.length == 0 || s.length() == 0) return res;
        
        int wordLen = words[0].length();
        int numWord = words.length;
        int windowLen = wordLen * numWord;
        int sLen = s.length();
        
        // 目標頻率表
        Map targetMap = new HashMap<>();
        for (String w : words) 
            targetMap.put(w, targetMap.getOrDefault(w, 0) + 1);
        
        // 多輪滑動（處理對齊問題）
        for (int offset = 0; offset < wordLen; offset++) {
            Map windowMap = new HashMap<>();
            int count = 0;      // 超額單字計數
            int start = offset; // 窗口起始
            
            for (int j = offset; j + wordLen <= sLen; j += wordLen) {
                String word = s.substring(j, j + wordLen);
                
                // 單字不在目標中 → 重置窗口
                if (!targetMap.containsKey(word)) {
                    windowMap.clear();
                    count = 0;
                    start = j + wordLen;
                    continue;
                }
                
                // 窗口滿時移除最左單字
                if (j >= start + windowLen) {
                    String leftWord = s.substring(start, start + wordLen);
                    start += wordLen;
                    int val = windowMap.get(leftWord);
                    if (val == 1) windowMap.remove(leftWord);
                    else windowMap.put(leftWord, val - 1);
                    if (val - 1 >= targetMap.get(leftWord)) count--;
                }
                
                // 加入新單字
                windowMap.put(word, windowMap.getOrDefault(word, 0) + 1);
                if (windowMap.get(word) > targetMap.get(word)) count++;
                
                // 檢查窗口有效性
                if (count == 0 && start + windowLen == j + wordLen) 
                    res.add(start);
            }
        }
        return res;
    }
}

複雜度分析

關鍵圖解

外層循環必要性：單字長度為 3 時，可能從索引 0、1、2 任一位置開始對齊，故需 wordLen 輪掃描。

常見陷阱與優化

• 單字重複：Map 計數機制天然處理 ["foo", "foo", "bar"] 此類情況
• 提前終止：start + windowLen > sLen 直接 break
• 字符編碼：適用 Unicode，substring 按字符而非位元組切分