# 030-substring-with-concatenation-of-all-words

## Question

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:

``````s: "barfoothefoobarman"
words: ["foo", "bar"]

You should return the indices: [0,9].
``````

## Thought Process

1. Brute Force
1. We simply break the string at different point to make the substring the length of total length of words
2. Time complexity O(nmw), where n is length of string, m is number of words, and w is length of word
3. Space complexity O(mw)
2. Split based on Word length
1. If we observed closely, we have done a lot of repeated word check
2. There are only w possible cut on the string, meaning the 0th to (w - 1)th position, where w is the length of the word
3. Time complexity O(n)
4. Space complexity O(n)

## Solution

``````class Solution {
public List<Integer> findSubstring(String s, String[] words) {
// this question is very similiar to slinding window for single letter, we
// can see the entire word as one letter and slide the window appropiately
List<Integer> res = new ArrayList<>();
if (s == null || words == null || words.length == 0) return res;
int n = s.length(), m = words.length, w = words[0].length();
int totalLen = m * w;
if (n < totalLen) return res;
// record the count for each word
Map<String, Integer> counts = new HashMap<>();
for (String word : words) {
counts.put(word, counts.getOrDefault(word, 0) + 1);
}
for (int i = 0; i <= n - totalLen; i++) {
String sub = s.substring(i, i + totalLen);
int lo = i , hi = i + totalLen - w;
Map<String, Integer> map = new HashMap<>(counts);
while (lo <= hi) {
String word = s.substring(lo, lo + w);
if (map.getOrDefault(word, 0) <= 0) break;
else map.put(word, map.get(word) - 1);
lo += w;
}
if (lo == i + totalLen) res.add(i);
}
return res;
}
}
``````
``````class Solution {
public List<Integer> findSubstring(String s, String[] words) {
// this question is very similiar to slinding window for single letter, we
// can see the entire word as one letter and slide the window appropiately
List<Integer> res = new ArrayList<>();
if (s == null || words == null || words.length == 0) return res;
int n = s.length(), m = words.length, w = words[0].length();
int totalLen = m * w;
if (n < totalLen) return res;
// record the count for each word
Map<String, Integer> counts = new HashMap<>();
for (String word : words) {
counts.put(word, counts.getOrDefault(word, 0) + 1);
}
// There are only w position to cut t
for (int i = 0; i < w; i++) {
int left = i, right = i;
int window = 0;
// while we still have enough characters for string
while (left + (m - window) * w <= n && right + w <= n) {
String cur = s.substring(right, right + w);
if (counts.containsKey(cur)) {
int count = counts.get(cur);
window++;
if (count > 0) {
counts.put(cur, count - 1);
} else {
String removed = s.substring(left, left + w);
while (!removed.equals(cur)) {
counts.put(removed, counts.get(removed) + 1);
left += w;
window--;
removed = s.substring(left, left + w);
}
left += w;
window--;
}
// reset if we dont have such word
} else {
while (left < right) {
String removed = s.substring(left, left + w);
counts.put(removed, counts.get(removed) + 1);
left += w;
window--;
}
left += w;
}
right += w;
}
while (left < right) {
String removed = s.substring(left, left + w);
counts.put(removed, counts.get(removed) + 1);
left += w;
}
}
return res;
}
}
``````