# Substring with Concatenation of All Words
**Difficulty:** HARD
[External](https://leetcode.com/problems/substring-with-concatenation-of-all-words)
Canonical: https://scaleengineer.com/dsa/problems/substring-with-concatenation-of-all-words
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Data structures:** Hash Table, String
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Samsung](https://scaleengineer.com/companies/samsung), [Zeta](https://scaleengineer.com/companies/zeta), [Media.net](https://scaleengineer.com/companies/media.net), [Roku](https://scaleengineer.com/companies/roku)
---
## Problem
You are given a string `s` and an array of strings `words`. All the strings of `words` are of **the same length**.

A **concatenated string** is a string that exactly 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 string because it is not the concatenation of any permutation of `words`.

Return an array of _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:**

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`.

**Example 2:**

**Input:** s = "wordgoodgoodgoodbestword", words = \["word","good","best","word"\]

**Output:** \[\]

**Explanation:**

There is no concatenated substring.

**Example 3:**

**Input:** s = "barfoofoobarthefoobarman", words = \["bar","foo","the"\]

**Output:** \[6,9,12\]

**Explanation:**

The substring starting at 6 is `"foobarthe"`. It is the concatenation of `["foo","bar","the"]`.  
The substring starting at 9 is `"barthefoo"`. It is the concatenation of `["bar","the","foo"]`.  
The substring starting at 12 is `"thefoobar"`. It is the concatenation of `["the","foo","bar"]`.

**Constraints:**

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

# Approaches
## Brute Force with Hashing
This approach iterates through every possible starting position of a concatenated substring in `s`. For each position, it checks if the following substring of length `numWords * wordLen` is a valid concatenation of words from the `words` array. This check is performed by using a hash map to count word frequencies within the substring and comparing it to the frequency map of the original `words` array.
**Time:** O(N * M * L) · **Space:** O(M * L)
**Pros:** Conceptually simple and straightforward to implement.; It correctly solves the problem without the complexity of generating permutations.
**Cons:** Highly inefficient due to redundant computations. For each starting position `i`, it re-evaluates the entire substring from scratch.; The time complexity is very high, which will likely cause a 'Time Limit Exceeded' (TLE) error on platforms like LeetCode for larger inputs.
### Explanation
The method begins by pre-calculating essential values: `numWords` (the count of words), `wordLen` (the length of a single word), and `substringLen` (the total length of the target substring). A reference frequency map, `wordCount`, is created from the input `words` array to know what a valid permutation should contain.

The main part of the algorithm is a loop that iterates through `s` from index `0` up to the last possible starting point for a valid substring. In each iteration, a substring of length `substringLen` is extracted. To verify if this substring is a valid concatenation, we build a second frequency map, `wordsSeen`, by chopping the substring into `wordLen`-sized chunks and counting them. Finally, we compare `wordsSeen` with `wordCount`. If they are equal, the starting index `i` is a valid solution and is added to our results.

```java
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

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

        int wordLen = words[0].length();
        int numWords = words.length;
        int substringLen = wordLen * numWords;
        List<Integer> result = new ArrayList<>();

        if (s.length() < substringLen) {
            return result;
        }

        Map<String, Integer> wordCount = new HashMap<>();
        for (String word : words) {
            wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);
        }

        for (int i = 0; i <= s.length() - substringLen; i++) {
            Map<String, Integer> wordsSeen = new HashMap<>();
            for (int j = 0; j < numWords; j++) {
                int wordStart = i + j * wordLen;
                String word = s.substring(wordStart, wordStart + wordLen);
                wordsSeen.put(word, wordsSeen.getOrDefault(word, 0) + 1);
            }

            if (wordCount.equals(wordsSeen)) {
                result.add(i);
            }
        }

        return result;
    }
}
```
### Algorithm
- Get the number of words `numWords`, the length of each word `wordLen`, and the total length of the concatenated substring `substringLen`.
- Create a frequency map `wordCount` for the words in the `words` array.
- Initialize an empty list `result` to store the starting indices.
- Iterate through the string `s` from index `i = 0` to `s.length() - substringLen`.
- For each `i`, extract the substring of length `substringLen`.
- Create a new frequency map `wordsSeen` for the words within this substring by breaking it into chunks of `wordLen`.
- Compare the `wordsSeen` map with the `wordCount` map.
- If the maps are identical, add the index `i` to the `result` list.
- Return the `result` list after checking all possible indices.

## Optimized Sliding Window
This approach significantly optimizes the search by using a sliding window technique. Since all words have the same length, `wordLen`, any valid concatenated substring must be composed of words that are aligned on a grid with a step size of `wordLen`. We can check all possible alignments by running `wordLen` separate passes over the string. Each pass uses a sliding window that moves `wordLen` characters at a time, efficiently updating word counts instead of re-computing them from scratch for each starting position.
**Time:** O(N * L) · **Space:** O(M * L)
**Pros:** Highly efficient, with a time complexity that is linear in the length of the input string `s` and word length `L`.; Avoids redundant work by intelligently sliding the window and updating counts incrementally.
**Cons:** The logic is more complex to understand and implement correctly compared to the brute-force approach.; It involves careful management of the sliding window, multiple pointers, and frequency maps.
### Explanation
The key insight is that we don't need to check every single starting index. A valid substring starting at index `k` will be composed of words at `k, k+L, k+2L, ...` where `L` is `wordLen`. This means we can iterate through the string `L` times, once for each possible remainder modulo `L` (i.e., `i = 0, 1, ..., L-1`).

For each starting offset `i`, we use a sliding window. We maintain a `left` pointer for the start of the window and a `j` pointer for the end. We slide `j` through the string in steps of `L`. We use a `seenWords` map to track word frequencies within the current window. 

- When a new word (at `j`) enters the window, we update `seenWords`. 
- If the new word is not in our target `wordCount` map, the window is invalid, so we reset it.
- If a word's count in `seenWords` becomes too high, we shrink the window from the `left` until the counts are valid.
- When the number of valid words in our window (`wordsFound`) reaches `numWords`, we've found a solution. We record the `left` index and then slide the window by one word to search for the next potential match.

This avoids re-computation and brings the complexity down significantly.

```java
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

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

        Map<String, Integer> wordCount = new HashMap<>();
        for (String word : words) {
            wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);
        }

        int wordLen = words[0].length();
        int numWords = words.length;
        List<Integer> result = new ArrayList<>();

        for (int i = 0; i < wordLen; i++) {
            int left = i;
            int wordsFound = 0;
            Map<String, Integer> seenWords = new HashMap<>();

            for (int j = i; j <= s.length() - wordLen; j += wordLen) {
                String word = s.substring(j, j + wordLen);

                if (wordCount.containsKey(word)) {
                    seenWords.put(word, seenWords.getOrDefault(word, 0) + 1);
                    wordsFound++;

                    while (seenWords.get(word) > wordCount.get(word)) {
                        String leftWord = s.substring(left, left + wordLen);
                        seenWords.put(leftWord, seenWords.get(leftWord) - 1);
                        wordsFound--;
                        left += wordLen;
                    }

                    if (wordsFound == numWords) {
                        result.add(left);
                        String leftWord = s.substring(left, left + wordLen);
                        seenWords.put(leftWord, seenWords.get(leftWord) - 1);
                        wordsFound--;
                        left += wordLen;
                    }
                } else {
                    seenWords.clear();
                    wordsFound = 0;
                    left = j + wordLen;
                }
            }
        }
        return result;
    }
}
```
### Algorithm
- Pre-calculate `wordLen`, `numWords`, and create a reference frequency map `wordCount` from `words`.
- Loop `i` from `0` to `wordLen - 1`. This outer loop handles all possible word alignments.
- For each `i`, initialize a sliding window with `left = i`, `wordsFound = 0`, and an empty `seenWords` map.
- Use a second pointer `j` to slide through the string from `i` in steps of `wordLen`.
- At each step `j`, extract the `word`.
- If `word` is in `wordCount`:
  - Update its count in `seenWords` and increment `wordsFound`.
  - If the count of `word` in `seenWords` exceeds `wordCount`, shrink the window from the `left` until it's valid again, updating `seenWords` and `wordsFound`.
  - If `wordsFound` equals `numWords`, a valid substring is found. Add `left` to the results, and slide the window one step to the right to continue the search.
- If `word` is not in `wordCount`, reset the window and maps, and move `left` to the position after the invalid word.
- Return the collected results.

# Solutions
### CSharp

```csharp
public class Solution {
    public IList < int > FindSubstring(string s, string[] words) {
        var cnt = new Dictionary < string,
            int > ();
        foreach(var w in words) {
            if (!cnt.ContainsKey(w)) {
                cnt[w] = 0;
            }++cnt[w];
        }
        int m = s.Length, n = words.Length, k = words[0].Length;
        var ans = new List < int > ();
        for (int i = 0; i < k; ++i) {
            var cnt1 = new Dictionary < string,
                int > ();
            int l = i, r = i, t = 0;
            while (r + k <= m) {
                var w = s.Substring(r, k);
                r += k;
                if (!cnt.ContainsKey(w)) {
                    cnt1.Clear();
                    t = 0;
                    l = r;
                    continue;
                }
                if (!cnt1.ContainsKey(w)) {
                    cnt1[w] = 0;
                }++cnt1[w];
                ++t;
                while (cnt1[w] > cnt[w]) {
                    --cnt1[s.Substring(l, k)];
                    l += k;
                    --t;
                }
                if (t == n) {
                    ans.Add(l);
                }
            }
        }
        return ans;
    }
}
```

### Java

```java
class Solution {
public
  List<Integer> findSubstring(String s, String[] words) {
    Map<String, Integer> cnt = new HashMap<>();
    for (String w : words) {
      cnt.merge(w, 1, Integer : : sum);
    }
    int m = s.length(), n = words.length;
    int k = words[0].length();
    List<Integer> ans = new ArrayList<>();
    for (int i = 0; i < k; ++i) {
      Map<String, Integer> cnt1 = new HashMap<>();
      int l = i, r = i;
      int t = 0;
      while (r + k <= m) {
        String w = s.substring(r, r + k);
        r += k;
        if (!cnt.containsKey(w)) {
          cnt1.clear();
          l = r;
          t = 0;
          continue;
        }
        cnt1.merge(w, 1, Integer : : sum);
        ++t;
        while (cnt1.get(w) > cnt.get(w)) {
          String remove = s.substring(l, l + k);
          l += k;
          cnt1.merge(remove, -1, Integer : : sum);
          --t;
        }
        if (t == n) {
          ans.add(l);
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> findSubstring(string s, vector<string> &words) {
    unordered_map<string, int> cnt;
    for (auto &w : words) {
      ++cnt[w];
    }
    int m = s.size(), n = words.size(), k = words[0].size();
    vector<int> ans;
    for (int i = 0; i < k; ++i) {
      unordered_map<string, int> cnt1;
      int l = i, r = i;
      int t = 0;
      while (r + k <= m) {
        string w = s.substr(r, k);
        r += k;
        if (!cnt.count(w)) {
          cnt1.clear();
          l = r;
          t = 0;
          continue;
        }
        ++cnt1[w];
        ++t;
        while (cnt1[w] > cnt[w]) {
          string remove = s.substr(l, k);
          l += k;
          --cnt1[remove];
          --t;
        }
        if (t == n) {
          ans.push_back(l);
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]: cnt = Counter(words) m, n = len(s), len(words) k = len(words[0]) ans = [] for i in range(k): cnt1 = Counter() l = r = i t = 0 while r + k <= m: w = s[r: r + k] r += k if w not in cnt: l = r cnt1 . clear() t = 0 continue cnt1[w] += 1 t += 1 while cnt1[w] > cnt[w]: remove = s[l: l + k] l += k cnt1[remove] -= 1 t -= 1 if t == n: ans . append(l) return ans

```