> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/algorithm-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/algorithm-practice/leetcode/two-pointers/30-substring-with-concatenation-of-all-words.md).

# 30 Substring with Concatenation of All Words

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

## 1. Question

You are given a string,**s**, and a list of words, **words**, that are all of the same length. Find all starting indices of substring(s) in **s** that is a concatenation of each word in **words** exactly once and without any intervening characters.

For example, given:\
**s**:`"barfoothefoobarman"`\
**words**:`["foo", "bar"]`

You should return the indices:`[0,9]`.\
(order does not matter).

## 2. Implementation

**(1) Two Pointers + Hash**

```java
class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        int n = words.length, wordLen = words[0].length();
        List<Integer> res = new ArrayList<>();
        Map<String, Integer> map = new HashMap<>();
        Map<String, Integer> seen = new HashMap<>();

        for (String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }

        for (int i = 0; i <= s.length() - wordLen * n; i++) {
            seen = new HashMap<>();
            int j = 0;

            for (; j < n; j++) {
                String word = s.substring(i + j * wordLen, i + (j + 1) * wordLen);

                if (!map.containsKey(word)) {
                    break;
                }

                seen.put(word, seen.getOrDefault(word, 0) + 1);
                if (seen.get(word) > map.get(word)) {
                    break;
                }
            }

            if (j == n) {
                res.add(i);
            }
        }
        return res;
    }
}
```

## 3. Time & Space Complexity

**Two Pointers:** 时间复杂度O(mn), m为s的长度，n为words里word的个数，空间复杂度O(n)