## Algorithm

Problem Name: 30. Substring with Concatenation of All Words

You are given a string `s` and an array of strings `words`. All the strings of `words` are of the same length.

A concatenated substring in `s` is a substring that contains all the strings of any permutation of `words` concatenated.

• For example, if `words = ["ab","cd","ef"]`, then `"abcdef"`, `"abefcd"`, `"cdabef"`, `"cdefab"`, `"efabcd"`, and `"efcdab"` are all concatenated strings. `"acdbef"` is not a concatenated substring because it is not the concatenation of any permutation of `words`.

Return the starting indices of all the concatenated substrings in `s`. You can return the answer in any order.

Example 1:

```Input: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0,9]
Explanation: Since words.length == 2 and words[i].length == 3, the concatenated substring has to be of length 6.
The substring starting at 0 is "barfoo". It is the concatenation of ["bar","foo"] which is a permutation of words.
The substring starting at 9 is "foobar". It is the concatenation of ["foo","bar"] which is a permutation of words.
The output order does not matter. Returning [9,0] is fine too.
```

Example 2:

```Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output: []
Explanation: Since words.length == 4 and words[i].length == 4, the concatenated substring has to be of length 16.
There is no substring of length 16 is s that is equal to the concatenation of any permutation of words.
We return an empty array.
```

Example 3:

```Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
Output: [6,9,12]
Explanation: Since words.length == 3 and words[i].length == 3, the concatenated substring has to be of length 9.
The substring starting at 6 is "foobarthe". It is the concatenation of ["foo","bar","the"] which is a permutation of words.
The substring starting at 9 is "barthefoo". It is the concatenation of ["bar","the","foo"] which is a permutation of words.
The substring starting at 12 is "thefoobar". It is the concatenation of ["the","foo","bar"] which is a permutation of words.
```

Constraints:

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

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
typedef struct item_s {
char *word;
int idx;
struct item_s *next;
} item_t;

typedef struct {
item_t *p;
int n;
} buff_t;

#define HF 1021

unsigned int hash_code(const char *s, int len) {
unsigned int hc = 5381;
char c;
while (len -- > 0) {
hc = hc * 33 + s[len];
}
return hc % HF;
}

item_t *lookup(item_t **ht, unsigned int hc, const char *w, int len) {
item_t *p = ht[hc];
while (p) {
if (!strncmp(p->word, w, len)) {
return p;
}
p = p->next;
}
return NULL;
}

int* findSubstring(char* s, char** words, int wordsSize, int* returnSize) {

item_t *ht[HF] = { 0 }, **sp, *p;
int *counts, *counts2, total, i;
char *w;
unsigned int hc;

int total_len, word_len;
int left, mid, right;

int *results;

if (wordsSize == 0) return NULL;

buff_t buff = { 0 };
buff.p = malloc(wordsSize * sizeof(item_t));
//assert(buff->p);
counts = calloc(wordsSize * 2, sizeof(int));
//assert(counts);
counts2 = &counts[wordsSize];
total = 0;

word_len = strlen(words[0]);
total_len = strlen(s);

sp = malloc(total_len * sizeof(item_t *));
//assert(sp);

results = malloc(total_len * sizeof(int));
//assert(results);
*returnSize = 0;

for (i = 0; i  <  wordsSize; i ++) {
w = words[i];
hc = hash_code(w, word_len);
p = lookup(ht, hc, w, word_len);
if (p) {
counts[p->idx] ++;
} else {
p = &buff.p[buff.n];

p->idx = buff.n ++;
p->word = w;

p->next = ht[hc];
ht[hc] = p;

counts[p->idx] = 1;
}
}

left = mid = right = 0;
while (right  < = total_len - word_len) {
w = &s[right];
hc = hash_code(w, word_len);
p = lookup(ht, hc, w, word_len);
if (!p) {
total = 0;
memset(counts2, 0, buff.n * sizeof(int));   // reset all counts
left ++;           // shift one character from left
mid = left;
right = left;      // reset right
} else {
sp[right] = p;
i = p->idx;
counts2[i] ++;
total ++;
while (counts2[i] > counts[i]) {
p = sp[mid];
mid += word_len;   // push out a word
counts2[p->idx] --;
total --;
}
if (total == wordsSize) {   // all are found
results[*returnSize] = mid;
(*returnSize) ++;
total = 0;
memset(counts2, 0, buff.n * sizeof(int));   // reset all counts
left = mid + 1;
mid = left;
right = left;
} else {
right += word_len;
}
}
}

free(buff.p);
free(counts);
free(sp);

return results;
}
``````
Copy The Code &

Input

cmd
s = "barfoothefoobarman", words = ["foo","bar"]

Output

cmd
[0,9]

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public List findSubstring(String s, String[] words) {
int numberOfWords = words.length;
int singleWordLength = words[0].length();
int totalSubstringLength = singleWordLength * numberOfWords;
Map < String, Integer> wordCount = new HashMap<>();
for (String word : words) {
wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);
}
List < Integer> result = new ArrayList<>();
for (int i = 0; i  <  singleWordLength; i++) {
slidingWindow(i, s, result, singleWordLength, totalSubstringLength, wordCount, numberOfWords);
}
return result;
}

private void slidingWindow(int left, String s, List < Integer> answer, int singleWordLength,
int totalSubstringLength, Map wordCount, int numberOfWords) {
Map wordsFound = new HashMap<>();
int wordsUsed = 0;
boolean excessWord = false;
int n = s.length();
for (int right = left; right  < = n - singleWordLength; right += singleWordLength) {
String currSubstring = s.substring(right, right + singleWordLength);
if (!wordCount.containsKey(currSubstring)) {
wordsFound.clear();
wordsUsed = 0;
excessWord = false;
left = right + singleWordLength;
} else {
while (right - left == totalSubstringLength || excessWord) {
String leftmostWord = s.substring(left, left + singleWordLength);
left += singleWordLength;
wordsFound.put(leftmostWord, wordsFound.get(leftmostWord) - 1);
if (wordsFound.get(leftmostWord) >= wordCount.get(leftmostWord)) {
excessWord = false;
} else {
wordsUsed--;
}
}
wordsFound.put(currSubstring, wordsFound.getOrDefault(currSubstring, 0) + 1);
if (wordsFound.get(currSubstring)  < = wordCount.get(currSubstring)) {
wordsUsed++;
} else {
excessWord = true;
}
if (wordsUsed == numberOfWords && !excessWord) {
}
}
}
}
}
``````
Copy The Code &

Input

cmd
s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]

Output

cmd
[]

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const findSubstring = function(s, words) {
if (words == null || words.length === 0 || !s) return []
const wh = {}
const slen = s.length
const wl = words[0].length
const len = words[0].length * words.length
words.forEach(el => {
if (wh[el]) wh[el]++
else wh[el] = 1
})
const res = []
for (let i = 0; i  <  slen - len + 1; i++) {
if (chk(wh, s.slice(i, i + len), wl, words.length)) res.push(i)
}
return res
}

function chk(hash, str, wl, num) {
const oh = {}
for (let i = 0; i  <  num; i++) {
let tmp = str.slice(i * wl, i * wl + wl)
if (oh[tmp]) oh[tmp]++
else oh[tmp] = 1
}
const keys = Object.keys(hash)
for (let i = 0; i  <  keys.length; i++) {
if (oh[keys[i]] !== hash[keys[i]]) return false
}
return true
}
``````
Copy The Code &

Input

cmd
s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]

Output

cmd
[6,9,12]

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def findSubstring(self, s, words):
if not s or not words: return []
cnt, l_words, l_word, cnt_words, res = collections.Counter(words), len(words[0]) * len(words), len(words[0]), len(words), []
for i in range(len(s) - l_words + 1):
cur, j = dict(cnt), i
for _ in range(cnt_words):
w = s[j:j + l_word]
if w in cur:
if cur[w] == 1: cur.pop(w)
else: cur[w] -= 1
else: break
j += l_word
if not cur: res += i,
return res
``````
Copy The Code &

Input

cmd
s = "barfoothefoobarman", words = ["foo","bar"]

Output

cmd
[0,9]

### #5 Code Example with C# Programming

```Code - C# Programming```

``````
using System.Collections.Generic;

namespace LeetCode
{
public class _030_SubstringWithConcatenationOfAllWords
{
public IList < int> FindSubstring(string s, string[] words)
{
var result = new List<int>();
var wordsLenght = words.Length;
var sLenght = s.Length;
if (sLenght == 0 || wordsLenght == 0) { return result; }

var wordLenght = words[0].Length;
var concatLenght = wordsLenght * wordLenght;

if (concatLenght > sLenght) { return result; }

var wordsMap = new Dictionary < string, int>();
foreach (var word in words)
{
if (wordsMap.ContainsKey(word))
{
wordsMap[word]++;
}
else
{
wordsMap[word] = 1;
}
}
IDictionary < string, int> used;

int i, j, count;
var subString = string.Empty;
bool allUsed = false;
for (i = 0; i  < = sLenght - concatLenght; i++)
{
used = new Dictionary(wordsMap);

for (j = i; j  < = sLenght - wordLenght; j += wordLenght)
{
subString = s.Substring(j, wordLenght);
if (used.TryGetValue(subString, out count))
{
if (count == 0) { break; }
used[subString]--;
}
else
{
break;
}
}

allUsed = true;
foreach (var pair in used)
{
if (pair.Value > 0) { allUsed = false; break; }
}

}

return result;
}
}
}
``````
Copy The Code &

Input

cmd
s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]

Output

cmd
[]