# 30. Substring with Concatenation of All Words

#### Hard

***

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:**

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

**Example 2:**

<pre><code>Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
<strong>Output:
</strong> []
</code></pre>

**Example 3:**

<pre><code>Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
<strong>Output:
</strong> [6,9,12]
</code></pre>

&#x20;

**Constraints:**

* `1 <= s.length <= 104`
* `1 <= words.length <= 5000`
* `1 <= words[i].length <= 30`
* `s` and `words[i]` consist of lowercase English letters.

```python
class Solution:
    def _findSubstring(self, l, r, n, k, t, s, req, ans):
        curr = {}
        while r + k <= n:
            w = s[r:r + k]
            r += k
            if w not in req:
                l = r
                curr.clear()
            else:
                curr[w] = curr[w] + 1 if w in curr else 1
                while curr[w] > req[w]:
                    curr[s[l:l + k]] -= 1
                    l += k
                if r - l == t:
                    ans.append(l)

    def findSubstring(self, s, words):
        #.
        if not s or not words or not words[0]:
            return []
        n = len(s)
        k = len(words[0])
        t = len(words) * k
        req = {}
        for w in words:
            req[w] = req[w] + 1 if w in req else 1
        ans = []
        for i in range(min(k, n - t + 1)):
            self._findSubstring(i, i, n, k, t, s, req, ans)
        return ans
        
```