Log inSign up
hardleetcodeNot Started

Substring with Concatenation of All Words

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Strings
Solve on leetcode
Lesson

Problem Statement

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"]. The substring starting at 9 is "foobar". It is the concatenation of ["foo","bar"].

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: Substrings at 6 ("foobarthe"), 9 ("barthefoo"), and 12 ("thefoobar") are all valid concatenations.

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the offset sliding window technique for uniform token sizes.
  • Maintain dynamic frequency matching across sliding chunk windows.
  • Handle non-dictionary words by resetting window boundaries in O(1).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Finding permutations of a fixed list of equal-length words concatenated together in a text.
  • Sliding window over fixed token chunks.

Algorithmic Decision Tree:

  • Finding permutations of a fixed list of equal-length words concatenated together in a text.
  • Sliding window over fixed token chunks.

Connected Patterns:

Find All Anagrams in a StringMinimum Window SubstringLongest Substring Without Repeating Characters

1. Naive Window Substring Slicing

Intuition

Let M = words.length and L = words[0].length. The total concatenation length is totalLen = M * L. Loop i from 0 to N - totalLen. For each i, slice M chunks of size L. Check if chunk frequency matches the expected word frequency map. If all M chunks match, record i.

When to apply: Basic baseline comparison.

Algorithm

  1. Compute wordCount map.
  2. Loop i from 0 to n - m * L:
  3. Create seen map.
  4. For j from 0 to m - 1:
  5. w = s.substr(i + j * L, L).
  6. If w not in wordCount: break.
  7. seen[w]++.
  8. If seen[w] > wordCount[w]: break.
  9. If all m words matched: res.push(i).
  10. Return res.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <unordered_map>
5
6class Solution {
7public:
8 std::vector<int> findSubstring(std::string s, std::vector<std::string>& words) {
9 std::vector<int> res;
10 if (s.empty() || words.empty()) return res;
11
12 int n = s.size(), m = words.size(), l = words[0].size();
13 if (n < m * l) return res;
14
15 std::unordered_map<std::string, int> counts;
16 for (const auto& w : words) counts[w]++;
17
18 for (int i = 0; i <= n - m * l; ++i) {
19 std::unordered_map<std::string, int> seen;
20 int j = 0;
21 while (j < m) {
22 std::string word = s.substr(i + j * l, l);
23 if (counts.find(word) == counts.end()) break;
24 seen[word]++;
25 if (seen[word] > counts[word]) break;
26 j++;
27 }
28 if (j == m) res.push_back(i);
29 }
30 return res;
31 }
32};
33
34int main() {
35 Solution sol;
36 std::vector<std::string> words = {"foo", "bar"};
37 auto ans = sol.findSubstring("barfoothefoobarman", words);
38 for (int x : ans) std::cout << x << " "; // 0 9
39 std::cout << std::endl;
40 return 0;
41}

Time & Space Complexity

  • Time complexity: O((N - M * L) * M * L) — Tests (N - M * L) positions, each performing M hash map lookups and substring operations of length L.
  • Space complexity: O(M * L)

Why Brute Force Doesn't Scale:

Sliding window advances in O(1) amortized chunk steps rather than rescanning M words.

Only two small frequency hash maps are maintained during sliding.

2. Trie Node Lookup Window Check

Intuition

Build a Trie from words, storing word IDs and frequencies at terminal nodes. When checking candidate window chunks, traverse the Trie instead of creating substring hashes. If invalid, break early.

When to apply: When speeding up dictionary lookups on large vocabularies.

Algorithm

  1. Insert all words into Trie.
  2. Loop i from 0 to n - m * l.
  3. Traverse m successive words using Trie transitions.
  4. Record valid start indices.
  5. Return result array.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <unordered_map>
5
6class Solution {
7public:
8 std::vector<int> findSubstring(std::string s, std::vector<std::string>& words) {
9 std::vector<int> res;
10 int n = s.size(), m = words.size(), l = words[0].size();
11 if (n < m * l) return res;
12
13 std::unordered_map<std::string, int> counts;
14 for (const auto& w : words) counts[w]++;
15
16 for (int i = 0; i <= n - m * l; ++i) {
17 std::unordered_map<std::string, int> seen;
18 int matched = 0;
19 for (int j = 0; j < m; ++j) {
20 std::string word = s.substr(i + j * l, l);
21 auto it = counts.find(word);
22 if (it == counts.end()) break;
23 if (++seen[word] > it->second) break;
24 matched++;
25 }
26 if (matched == m) res.push_back(i);
27 }
28 return res;
29 }
30};
31
32int main() {
33 Solution sol;
34 std::vector<std::string> words = {"foo", "bar"};
35 auto ans = sol.findSubstring("barfoothefoobarman", words);
36 for (int x : ans) std::cout << x << " "; // 0 9
37 return 0;
38}

Time & Space Complexity

  • Time complexity: O((N - M * L) * M * L) — Trie lookup is O(L) per chunk without string hashing overhead.
  • Space complexity: O(M * L)

3. Offset-Shifted Sliding Window (Optimal O(N))

Intuition

Since each word has length L, any valid concatenation must start at some index modulo L. Run L independent sliding windows starting at offset from 0 to L - 1. For each offset: maintain left = offset, right = offset, count = 0 (number of valid words in current window), and seen map. Advance right by L. If the word w = s[right...right+L] is in counts: add to seen. While seen[w] > counts[w]: shrink left by L, decrement seen[s[left...left+L]], and count--. If count == M: record left. If w is not in counts: clear seen, set count = 0, and set left = right + L.

When to apply: The standard gold standard solution for linear time complexity.

Algorithm

  1. Let n = s.length, m = words.length, l = words[0].length.
  2. Build counts frequency map of words.
  3. For offset from 0 to l - 1:
  4. left = offset, right = offset, count = 0, seen = {}.
  5. While right + l <= n:
  6. w = s.substr(right, l); right += l.
  7. If w in counts:
  8. seen[w]++; count++.
  9. While seen[w] > counts[w]:
  10. leftWord = s.substr(left, l); seen[leftWord]--; count--; left += l.
  11. If count == m: res.push(left).
  12. Else:
  13. seen.clear(); count = 0; left = right.
  14. Return res.

Multi-Offset Rolling Word Chunk Sliding Window

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [bar, foo, the, foo, bar, man]
Current operationSTEP 1 OF 6
Observation: Words have uniform length $W = 3$ and count $K = 2$ (total window 6)
Visual state
Values and pointers at this exact step
array
S
bar
foo
the
foo
bar
man
0
↑ Offset 0: Window 0..6 ["bar", "foo"]
1
2
3
4
5
Variables at this step
wordLen
3
wordCount
2
totalWindowLen
6
targetFreq
{"foo":1,"bar":1}
windowFreq
{"bar":1,"foo":1}
match
true
Why this step matters

Observation: Words have uniform length W = 3 and count K = 2 (total window 6). At index 0, chunks are "bar" and "foo".

Decision: Chunks match { bar: 1, foo: 1 } identically. Record starting index 0.

Invariant: Window chunk frequencies match target multiset.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <unordered_map>
5
6class Solution {
7public:
8 std::vector<int> findSubstring(std::string s, std::vector<std::string>& words) {
9 std::vector<int> res;
10 if (s.empty() || words.empty()) return res;
11
12 int n = s.size(), m = words.size(), l = words[0].size();
13 if (n < m * l) return res;
14
15 std::unordered_map<std::string, int> counts;
16 for (const auto& w : words) counts[w]++;
17
18 for (int offset = 0; offset < l; ++offset) {
19 int left = offset, right = offset, count = 0;
20 std::unordered_map<std::string, int> seen;
21
22 while (right + l <= n) {
23 std::string w = s.substr(right, l);
24 right += l;
25
26 if (counts.find(w) != counts.end()) {
27 seen[w]++;
28 count++;
29
30 while (seen[w] > counts[w]) {
31 std::string leftWord = s.substr(left, l);
32 seen[leftWord]--;
33 count--;
34 left += l;
35 }
36
37 if (count == m) {
38 res.push_back(left);
39 }
40 } else {
41 seen.clear();
42 count = 0;
43 left = right;
44 }
45 }
46 }
47 return res;
48 }
49};
50
51int main() {
52 Solution sol;
53 std::vector<std::string> words = {"foo", "bar"};
54 auto ans = sol.findSubstring("barfoothefoobarman", words);
55 for (int x : ans) std::cout << x << " "; // 0 9
56 std::cout << std::endl;
57 return 0;
58}

Time & Space Complexity

  • Time complexity: O(L * (N / L)) = O(N) — Across all L offsets, every word chunk is visited by the left and right pointers at most twice.
  • Space complexity: O(M * L) for hash maps

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Naive Substring Chunk VerificationO((N - M * L) * M * L)O(M * L)Simple nested loop checking each candidate index.Repeatedly slices strings, too slow for tight time limits.
2.Offset-Shifted Sliding Window (Optimal)OptimalO(L * (N / L)) = O(N)O(M * L)Each character is processed at most twice per offset; strictly optimal linear runtime.Requires managing L separate sliding window passes.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Stepping by 1 character inside the inner sliding window instead of stepping by word length L.

Pitfall 2:

Resetting left to left + 1 instead of right when encountering a non-dictionary word.

Crucial Edge Cases to Validate:

  • s length smaller than total words length (n < m * l): Returns [] immediately.
  • Duplicate words in dictionary (e.g. words = [word, word]): Frequency map checks seen[w] > counts[w] enforcing exact counts.
  • All words identical in s (e.g. aaaaa): Sliding window shrinks smoothly one word chunk at a time.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the time complexity reduction from O(N * M * L) to O(N) by applying L offset sliding windows.
  2. Walk through how non-dictionary words trigger immediate O(1) window resets.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why are exactly L sliding window passes required (where L is word length)?

Back to DSA Sheet