# 30. Substring with Concatenation of All Words

[Link](https://leetcode.com/problems/substring-with-concatenation-of-all-words/description/)

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.

**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: []
```

**Solution**

TimeComplexitiy : O(n) where n is the s.length

SpaceComplexity: O(m), where m is words.length

```
  public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ret = new ArrayList<>();
        if (words.length == 0)
            return ret;

        HashMap<String, Integer> map = new HashMap<>();
        for (String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }
        int wordLength = words[0].length();
        int count = words.length;
        int minSize = count * wordLength;
        for (int i = 0; i <= s.length() - minSize; i++) {
            int j = 0;
            HashMap<String, Integer> seens = (HashMap<String, Integer>) map.clone();
            while (j < count) {
                String target = s.substring(i + j * wordLength, i + (j * wordLength) + wordLength);
                if (seens.containsKey(target)) {
                    if (seens.get(target) > 0) {
                        seens.put(target, seens.get(target) - 1);
                    } else {
                        break;
                    }
                } else {
                    break;
                }
                j++;
                if (count == j) {
                    ret.add(i);
                }
            }
        }
        return ret;
    }
```
