# Leetcode 解題速記 30. Substring with Concatenation of All Words
###### tags: `LeetCode` `C++`
題敘:
---
You are given a string s and an array of strings words of the same length. Return all starting indices of substring(s) in s that is a concatenation of each word in words exactly once, in any order, and without any intervening characters.

You can return the answer in any order.

Example 1:

Input: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoo" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.

Example 2:

Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output: []

Example 3:

Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
Output: [6,9,12]

測資範圍:
---
* `1 <= s.length <= 104`
* `1 <= words.length <= 5000`
* `1 <= words[i].length <= 30`
* `s and words[i] consist of lowercase English letters.`

解題筆記:
---
這題子字串我們使用的解題方式是slide window，並且用雙指針實現。

首先，我們需要hashmap去記錄當前所有子字串還未被使用的次數，因此開頭先由一個迴圈將word中所有可用的字都記錄進去。

接下來檢查字串的部分，window的寬度跟子字串寬度相同，一次向右移動一個字元。
假設子字串長度為3，s的長度為24，我們第一次檢查的index是0,3,6,9,12,15,18,21，第二次檢查的index就是1,4,7,10,13,16,19，以此類推，剩餘長度不足子字串長度時終止，

每當檢查到一個合法子字串，就將hashmap中相應的值-1，同時，如果hashmap中，該子字串剩餘可用次數>=0時，代表我們沒有用超過可用次數，因此紀錄合法子字串的變數count要+1。

每次迭代中，若是檢查到window的寬度過大，就要將左指針向右移。因此，右移過程中丟到的子字串，也要將相應hashmap中使用次數+1回去，同時，若是剩餘使用次數大於0，代表還沒滿足將所有子字串都使用的條件，因此count要-1。

最後一直迭代到count與words中合法子字串的數量相同，就代表這是一個合法組合，紀錄該組合的起始index，放進vector中統一回傳。

程式碼:
---

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ans;
        unordered_map<string, int> m1;
        int len = words[0].size();
        int n = s.length();
        int m = words.size();
        for (const string& it : words)
        {
            m1[it]++;
        }
        for (int i = 0; i < len; i++)
        {
            int count = 0;
            unordered_map<string, int> temp = m1;
            for (int j = i; j <= n - len; j += len)
            {
                string current = s.substr(j, len);
                temp[current]--;
                if (temp[current] >= 0)
                {
                    count++;
                }

                int pop_start = j - m * len;
                if (pop_start >= 0)
                {
                    string pop_word = s.substr(pop_start, len);
                    temp[pop_word]++;
                    if (temp[pop_word] > 0)
                    {
                        count--;
                    }
                }
                if (count == m)
                {
                    ans.push_back(pop_start + len);
                }
            }
        }
        return ans;
    }
};