# Substring with Concatenation of All Words

The key to this problem is that we can split the string s into groups. Let's say the length of word in word dictionary is l, then we can first find start index with the string splited at 0, l, 2 * l, 3 * l, .... Then we move all these indexes one step forward and try to find start index with words start at 1, l + 1, 2 * l + 1, 3 * l + 1, .... We keep moving these indexes until we meet l - 1, 2 * l - 1, 3 * l - 1, 4 * l - 1, ....

For each of these groups, we can apply sliding window method. Let a and b be two index, we always keeps the words between a and b are in the dictionary and add a to result if substring between a and b is a concatenations of all words. As we will visit every index in the string once so even we have two loops in the program, the time complexity will be .

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

int l = words[0].length();
int n = words.length;

if (l == 0) return result;
if (s.length() < l * n) return result;

HashMap<String, Integer> wordsCount = new HashMap<String, Integer>();

for (String w : words) {
if (wordsCount.containsKey(w)) {
wordsCount.put(w, wordsCount.get(w) + 1);
} else {
wordsCount.put(w, 1);
}
}

String[] splited = new String[s.length() - l + 1];

for (int i = 0; i < splited.length; i++) {
splited[i] = s.substring(i, i + l);
}

for (int i = 0; i < l; i++) {
int count = 0;
int a = i;
HashMap<String, Integer> partCount = new HashMap<String, Integer>();

for (int b = i; b < splited.length; b += l) {
String word = splited[b];

if (!wordsCount.containsKey(word)) {
a = b + l;
partCount.clear();
count = 0;
continue;
}

if (partCount.containsKey(word)) {
partCount.put(word, partCount.get(word) + 1);
count++;
} else {
partCount.put(word, 1);
count++;
}

while (partCount.get(word) > wordsCount.get(word)) {
String removeWord = splited[a];
partCount.put(removeWord, partCount.get(removeWord) - 1);
count--;
a += l;
}

if (count == words.length) {