# [30\. Substring with Concatenation of All Words](https://leetcode.com/problems/substring-with-concatenation-of-all-words/)

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words)
    {
        // 每個單字的長度都相同，為 n
        int n = words[0].size();
        
        // 計算總共有幾個單字
        int wordCounts = words.size();
        
        unordered_map<string,int> freq;
        
        // 計算每個單字出現的頻率
        for (int i = 0; i < wordCounts; i++)
        {
            freq[words[i]]++;
        }
                
        vector<int> res;

        // 一個指標 start 走訪一個單字的長度 n
        for (int start = 0; start < n; ++start)
        {
            // 兩個指標 i, j
            // i 為右邊界
            // j 為左邊界
            int i = start;
            int j = i;
            int cnt = 0;
            
            // 記錄目前的子串中每個單字的出現次數
            unordered_map<string, int> m;
            
            // 走訪字串 s
            while (j < s.size())
            {   
                // 如果子串中出現了一個不在 words 中的單字，清空 m，並且將指針 i 和 j 向前移動一個單字的長度。
                if (!freq.count(s.substr(j, n)))
                {
                    // 清空 m
                    m.clear();
                    // 清空 cnt
                    cnt = 0;
                    // i, j 跳到下一個起始點
                    j += n;
                    i = j;
                }
                // 如果子串中所有單字的出現次數均不超過 words 中該單字的出現次數，我們將指針 j 向前移動一個單字的長度，同時增加相應的計數。
                else if (m[s.substr(j, n)] < freq[s.substr(j, n)])
                {
                    m[s.substr(j, n)]++;
                    cnt++;
                    j += n;
                }
                // 如果子串中某個單字的出現次數超過了 words 中該單字的出現次數，我們將指針 i 向前移動一個單字的長度，同時將相應的計數減少。
                else if (m[s.substr(j, n)] == m[s.substr(j, n)])
                {
                    m[s.substr(i, n)]--;
                    i += n;
                    cnt--;
                }
                
                // 當找到一個包含 words 中所有單字的子串時，將其起始 index 加入結果 res 中。
                if (cnt == wordCounts)
                {
                    res.push_back(i);
                    m[s.substr(i, n)]--;
                    // i 向前移動 n 的距離
                    i += n;
                    cnt--;
                }                                     
            }
        }
        
        return res;
    }
};

:::success
- 時間複雜度：$O()$
- 空間複雜度：$O()$
:::