30. Substring with Concatenation of All Words

這是一個經典的 LeetCode 難題，涉及字串處理和滑動視窗 (Sliding Window) 的技巧。

🧐 題目解釋：子串與所有單詞的串聯 (Substring with Concatenation of All Words)
這道題目的目標是從一個主字串 s 中，找出所有子字串的起始索引，這些子字串必須滿足以下條件：

這個子字串的長度必須恰好等於 words 陣列中所有單詞的總長度。

這個子字串必須由 words 陣列中所有單詞以任意順序（即某種排列組合）不重疊地依序串聯而成。

關鍵參數定義：
L: 每個單詞的長度（words[i].length）。題目保證所有單詞長度相同。

N: 單詞的數量（words.length）。

T: 目標子字串的總長度，T=L×N。

💡 核心思路：
由於目標子字串的總長度 T 是固定的，且它必須由 words 中所有單詞構成，因此這很適合使用滑動視窗的方法來解決。我們需要做的是：

統計單詞頻率（Word Frequency）：首先計算 words 陣列中每個單詞出現的次數，作為我們的目標計數。

設定滑動視窗：在字串 s 上設定一個長度為 T 的視窗。

視窗內的檢查：對於每個視窗，將其分解為 N 個長度為 L 的子單詞，然後檢查這些子單詞的頻率是否與我們的目標計數完全一致。

優化滑動：由於單詞的長度 L 決定了子單詞的邊界，我們可以利用 L 來優化滑動過程。只需要從 s 的起始位置 0 到 L−1 分別開始進行滑動視窗檢查即可。

💻 Java 解題教學 (使用優化的滑動視窗)

1. 數據結構準備
   我們需要兩個 Hash Map 來追蹤單詞的計數：

counts: 儲存 words 陣列中目標單詞及其出現的頻率（目標計數）。

temp: 儲存當前滑動視窗中遇到的單詞及其出現的頻率（視窗內計數）。

2. 算法步驟
   步驟一：初始化目標計數
   遍歷 words 陣列，計算每個單詞的頻率，並存入 counts 中。

步驟二：多起點滑動視窗
由於單詞長度 L 限制了單詞的起點（例如 L=3，則可能的單詞起點是 0,3,6,… 或 1,4,7,… 或 2,5,8,…），我們需要以 s 的前 L 個索引 i=0,1,…,L−1 作為不同組別的起始點，分別進行滑動視窗檢查。

對於每個起始點 i：

設定滑動視窗的左右邊界：

left = i（視窗的起始索引）

right（視窗的結束索引，每次移動 L）

重置 temp（視窗內計數）和 foundWords 數量。

從 right = i 開始，每次向右移動 L 的長度：

提取單詞：提取 s 中從 right 開始、長度為 L 的子字串 w。

檢查：

如果 w 不在 counts 中：表示遇到了無效單詞。此時，當前視窗（從 left 到 right）無效。我們重置 temp，foundWords 為 0，並將 left 移到 right + L，開始一個新的視窗。

如果 w 在 counts 中：

將 w 及其頻率更新到 temp 中。

增加 foundWords 計數。

收縮視窗 (Shrink)：如果 w 在 temp 中的數量超過了 counts 中的目標數量，則表示 w 多了。我們需要從 left 開始向右收縮，每次移動 L，直到多餘的 w 被移除。

找到匹配：如果 foundWords 恰好等於 N（即視窗長度 T 且單詞計數匹配），說明我們找到了符合條件的子字串。將 left 加入結果列表。然後，為了繼續尋找下一個匹配，我們將 left 右移 L（移除最左邊的單詞），並更新 temp 和 foundWords，讓視窗繼續滑動。