# 30. Substring with Concatenation of All Words (Hard)

https://leetcode.com/problems/substring-with-concatenation-of-all-words/

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 = "wordgoodgoodgoodbestword",
words = ["word","good","best","word"]
Output: `[]`
```

## Solutions

``````class Solution {

// This problem should not be classified as hard.

public List<Integer> findSubstring(String s, String[] words) {

if (s == null || s.length() == 0 || words.length == 0) {
return ans;
}

// length of each word
int wordLen = words[0].length();

// length of the combination of all the words
int combLen = wordLen * words.length;

// Combination string should not be longer than given s
if (s.length() < combLen) {
return ans;
}

// Keep the word frequency in words
Map<String, Integer> wordsFreqMap = new HashMap<>();

// Initialization
for (int i = 0; i < words.length; i++) {
if (!wordsFreqMap.containsKey(words[i])) {
wordsFreqMap.put(words[i], 0);
}

wordsFreqMap.put(words[i], wordsFreqMap.get(words[i]) + 1);
}

for (int i = 0; i <= s.length() - combLen; i++) {

boolean matched = true;

// Keep the frequency of matched words in s
Map<String, Integer> matchedFreqMap = new HashMap<>();

String ss = s.substring(i, i + combLen);
for (int j = 0; j < words.length; j++) {
String sss = ss.substring(j * wordLen, (j + 1) * wordLen);
if (!matchedFreqMap.containsKey(sss)) {
matchedFreqMap.put(sss, 0);
}

matchedFreqMap.put(sss, matchedFreqMap.get(sss) + 1);

// if word sss does not exist in the dictionary or its frequency larger than required, we take it unmatched.
if (!wordsFreqMap.containsKey(sss) || matchedFreqMap.get(sss) > wordsFreqMap.get(sss)) {
matched = false;
break;
}
}

if (matched) {
}
}

return ans;
}
}
``````