# Substring with Concatenation of All Words

#1

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 "barfoor" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.
```

Example 2:

```Input:
s = "wordgoodstudentgoodword",
words = ["word","student"]
Output: `[]`
```

#2

The key here is to observe all the words have the same length. Using this, you can form a word map, check from every character in the string, if the length of the word exists in the map, then check if the no of occurences match.

``````func findSubstring(s string, words []string) []int {

result := make([]int, 0)
if len(s) == 0 || len(words) ==0 { return result}

wl := len(words[0])
wordMap := make(map[string]int, 0)
wordsLen := len(words)

for i:=0 ;i<len(words);i++{
wordMap[words[i]] += 1
}

// total nof of chars in all words
totalCharLen := wl * wordsLen

for i:=0;i<len(s) - totalCharLen + 1;i++{
seen := make(map[string]int, 0)
j := 0
for j<wordsLen{
word := s[i+j*wl:i+(j+1)*wl]
if _, ok := wordMap[word]; ok {
seen[word] += 1
if seen[word] > wordMap[word]{
break
}
} else{
break
}
j++
}
if j==wordsLen{
result = append(result, i)
}
}

return result
}

``````