Substring with Concatenation of All Words

Q: What is the time complexity of Substring with Concatenation of All Words?

O(n * word_len). The algorithm iterates over word_len offsets, and for each offset, it scans the string in increments of word_len, processing each word once. Each word is added and removed from the window at most once, resulting in O(n) operations per offset and O(n * word_len) overall.

Q: What pattern does Substring with Concatenation of All Words use?

The Pattern: Sliding Window (Fixed-Size Chunk Partitioning) The Heuristic: When searching for concatenations of fixed-length words in a string, partition the string into word-length segments and slide a window over these segments, adjusting boundaries to maintain valid word counts and efficiently find all matches.

Hard Sliding Window

Problem

Given a string s and an array of strings words, return all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.

1 ≤ s.length ≤ 10⁴
1 ≤ words.length ≤ 5000
1 ≤ words[i].length ≤ 30
s and words[i] consist of lowercase English letters

Example

Input: s = "barfoothefoobarman", words = ["foo","bar"]

Output: [0,9]

The substrings starting at indices 0 and 9 are "barfoo" and "foobar" respectively, both concatenations of the words "foo" and "bar" without any extra characters. A brute-force approach would check every substring of length equal to total concatenation length, verifying if it contains all words exactly once, which is inefficient. The sliding window approach partitions the string into word-length segments and slides over these segments, maintaining counts of seen words and adjusting the window to ensure no word is overused. This method efficiently finds all valid starting indices in O(n) time relative to the string length.

Approach

Straightforward Solution

A brute-force solution would check every substring of length total_len and verify if it contains all words exactly once by counting frequencies. This approach is O(n * m * k) where n is string length, m is number of words, and k is word length, which is too slow for large inputs.

Core Observation

The problem reduces to finding all substrings of length equal to the total length of all words concatenated, where the substring is composed of the words in any order, each exactly once. Since all words have the same length, the string can be segmented into fixed-size chunks, enabling a sliding window approach that moves in increments of word length.

Path to Optimal

The key insight is to slide over the string in word_len increments, maintaining a window of words and their counts. By moving the window and adjusting counts when a word is overused or invalid, the algorithm avoids redundant checks and achieves linear time relative to the string length. This approach leverages the fixed word length to partition the string and uses a hash map to track word frequencies efficiently.

Optimal Approach

Iterate over possible offsets from 0 to word_len - 1 to cover all possible alignments. For each offset, use two pointers (left and right) to define a sliding window of words. Expand the window by adding words at the right pointer and update counts. If a word is overused, shrink the window from the left until counts are valid. When the window contains exactly all words, record the starting index. This method ensures all valid substrings are found in O(n) time with O(m) space.

Time

O(n * word_len)

The algorithm iterates over word_len offsets, and for each offset, it scans the string in increments of word_len, processing each word once. Each word is added and removed from the window at most once, resulting in O(n) operations per offset and O(n * word_len) overall.

Space

O(m)

The auxiliary space is dominated by the hash maps storing the target word counts and the current window counts, both proportional to the number of words m.

Pattern Spotlight

Sliding Window (Fixed-Size Chunk Partitioning)

When searching for concatenations of fixed-length words in a string, partition the string into word-length segments and slide a window over these segments, adjusting boundaries to maintain valid word counts and efficiently find all matches.

Solution

1class Solution:
  def findSubstring(self, s: str, words: List[str]) -> List[int]:
      if not s or not words:
          return []
5
      word_len = len(words[0])
      num_words = len(words)
      total_len = word_len * num_words
9
      target = {}
      for w in words:
          target[w] = target.get(w, 0) + 1
13
      result = []
15
      for offset in range(word_len):
          left = offset
          window = {}
          words_used = 0
20
          for right in range(offset, len(s) - word_len + 1, word_len):
              word = s[right:right + word_len]
23
              if word in target:
                  window[word] = window.get(word, 0) + 1
                  words_used += 1
27
                  while window[word] > target[word]:
                      left_word = s[left:left + word_len]
                      window[left_word] -= 1
                      left += word_len
                      words_used -= 1
33
                  if words_used == num_words:
                      result.append(left)
36
              else:
                  window.clear()
                  words_used = 0
                  left = right + word_len
41
      return result

Step-by-Step Solution

Validate Inputs and Derive Fixed Word Parameters

3if not s or not words:
4    return []
6word_len = len(words[0])
7num_words = len(words)
8total_len = word_len * num_words
14result = []

Objective

Ensure the inputs are valid and compute the structural parameters needed for the sliding window algorithm.

Key Insight

Because all words share the same length, the string can be processed in fixed-size word segments. Determining word length and word count early enables the sliding window to move in consistent increments.

Interview Quick-Check

Core Logic

Early validation prevents unnecessary computation and avoids accessing words[0] when the list is empty.

State & Boundaries

The fixed word length is the structural property that makes the sliding window approach possible.

Build Frequency Map of Target Words

10target = {}
11for w in words:
12    target[w] = target.get(w, 0) + 1

Objective

To create a hash map that counts how many times each word appears in the input list, serving as the target frequency for valid substrings.

Key Insight

Counting the frequency of each word in words is essential to verify if a sliding window contains exactly the right number of each word. This map acts as a reference to detect overuse or missing words during the window traversal.

Interview Quick-Check

Core Logic

The target frequency map enables O(1) checks to determine if a word is expected and how many times it should appear.

Common Pitfalls & Bugs

Failing to build this map correctly leads to incorrect validation of candidate substrings.

Slide Window Over String in Word-Length Increments for Each Offset

16for offset in range(word_len):
  left = offset
  window = {}
  words_used = 0
  for right in range(offset, len(s) - word_len + 1, word_len):
      word = s[right:right + word_len]
      if word in target:
          window[word] = window.get(word, 0) + 1
          words_used += 1
          while window[word] > target[word]:
              left_word = s[left:left + word_len]
              window[left_word] -= 1
              left += word_len
              words_used -= 1
          if words_used == num_words:
              result.append(left)
      else:
          window.clear()
          words_used = 0
          left = right + word_len

Objective

To iterate over the string starting at each possible offset and use a sliding window to find valid concatenations of words.

Key Insight

Because all words have the same length, the string can be partitioned into word-length segments. Sliding over these segments with two pointers allows efficient tracking of word counts in the current window. Adjusting the window when a word is overused or invalid maintains correctness and avoids redundant checks.

Interview Quick-Check

Core Logic

Sliding the window in increments of word length and adjusting boundaries when counts exceed target frequencies ensures all valid substrings are found without overlap or omission.

State & Boundaries

The window expands by moving the right pointer and shrinks by moving the left pointer, maintaining the invariant that no word count exceeds its target.

Common Pitfalls & Bugs

Not resetting the window state when encountering a word not in the target map leads to incorrect matches.

Complexity

Each word is processed at most twice (once when added and once when removed), ensuring linear time complexity per offset.

Return All Valid Starting Indices

42	`return result`

Objective

To output the list of all starting indices where valid concatenations of all words occur.

Key Insight

After processing all offsets and sliding windows, the collected indices represent all substrings matching the concatenation criteria. Returning this list completes the solution.

Interview Quick-Check

Core Logic

Returning the accumulated result list provides the final answer as required by the problem.

Line Analysis

This solution has 7 Critical lines interviewers watch for.

Line 28 Critical

while window[word] > target[word]:

While the current word's count exceeds its target frequency, shrink the window from the left.

This loop is the core sliding window adjustment that ensures the window remains valid by removing words from the left until the frequency constraints are satisfied, enabling efficient detection of valid concatenations.

Line 3 Critical

if not s or not words:

Check if input string or words list is empty.

An empty string or empty words list means no valid concatenations can exist, so returning an empty list immediately avoids unnecessary computation.

Line 16 Critical

for offset in range(word_len):

Iterate over all possible offsets from 0 to word_len - 1.

Considering all offsets ensures that all possible alignments of word-length segments are checked, preventing missed matches due to misalignment.

Line 21 Critical

for right in range(offset, len(s) - word_len + 1, word_len):

Iterate over the string in steps of word_len starting from the offset.

Stepping by word length ensures the window moves over valid word-sized segments, maintaining alignment with the words in the list.

Line 24 Critical

if word in target:

Check if the extracted word is in the target frequency map.

Only words in the target list are relevant; encountering a non-target word invalidates the current window and requires resetting state.

Line 34 Critical

if words_used == num_words:

Check if the window contains exactly all words.

When the number of words used matches the total number of words, the current window is a valid concatenation and its start index should be recorded.

Line 37 Critical

else:

Handle the case where the current word is not in the target map.

Encountering an invalid word breaks the current window, so the window state must be reset to start fresh after this word.

Line 4 Core

return []

Return an empty list for empty input edge cases.

This early return handles trivial cases efficiently and prevents errors in subsequent logic that assumes non-empty inputs.

Line 6 Core

word_len = len(words[0])

Determine the fixed length of each word.

All words share the same length, which allows the string to be partitioned into word-sized chunks and enables the sliding window to move in increments of word_len.

Line 10 Core

target = {}

Initialize a dictionary to count target word frequencies.

This dictionary forms the baseline for validating candidate substrings by tracking how many times each word should appear.

Line 12 Core

target[w] = target.get(w, 0) + 1

Increment the count for the current word in the target map.

Accurately counting occurrences ensures the algorithm can detect when a word is overused or missing in the sliding window.

Line 18 Core

window = {}

Initialize a dictionary to count words in the current window.

Tracking the frequency of words in the current window is essential to compare against the target frequencies and maintain validity.

Line 22 Core

word = s[right:right + word_len]

Extract the current word-sized substring from the string.

Extracting the word allows the algorithm to check if it is part of the target words and update counts accordingly.

Line 25 Core

window[word] = window.get(word, 0) + 1

Increment the count of the current word in the window map.

Updating the window counts tracks how many times each word appears in the current substring, enabling validation against the target counts.

Line 29 Core

left_word = s[left:left + word_len]

Extract the word at the left pointer of the window.

Identifying the leftmost word allows decrementing its count as the window shrinks, maintaining accurate frequency tracking.

Line 30 Core

window[left_word] -= 1

Decrement the count of the leftmost word in the window map.

Reducing the count reflects the removal of this word from the current window, keeping the frequency map consistent.

Line 31 Core

left += word_len

Move the left pointer forward by one word length.

Advancing the left pointer shrinks the window, removing excess words and restoring validity.

Line 35 Core

result.append(left)

Append the current left pointer index to the result list.

Recording the start index of a valid substring fulfills the problem requirement to return all such indices.

Line 38 Core

window.clear()

Clear the window frequency map.

Resetting the window counts removes all previous words, preparing for a new window starting after the invalid word.

Line 40 Core

left = right + word_len

Move the left pointer to the position after the invalid word.

Advancing the left pointer skips the invalid word, starting a new window from the next possible valid position.

Line 7 Core

num_words = len(words)

Determine how many words must appear in each valid substring.

Knowing the number of words lets the algorithm detect when the sliding window contains exactly the required number of valid words.

Line 17 Core

left = offset

Initialize the left pointer of the sliding window at the current offset.

The left pointer marks the start of the current window and moves forward to shrink the window when necessary.

Line 19 Core

words_used = 0

Initialize a counter for the number of words used in the current window.

This counter helps quickly determine when the window contains all required words, enabling efficient detection of valid substrings.

Line 26 Core

words_used += 1

Increment the count of words used in the current window.

This count helps determine when the window contains the full set of words, signaling a potential valid substring.

Line 32 Core

words_used -= 1

Decrement the count of words used in the window.

Updating the count reflects the removal of a word from the window, ensuring accurate tracking of window size.

Line 39 Core

words_used = 0

Reset the count of words used in the window to zero.

Resetting the count ensures the window size tracking is accurate for the new window.

Line 42 Core

return result

Return the list of all valid starting indices found.

Returning the accumulated results completes the algorithm and provides the required output.

Line 8 Standard

total_len = word_len * num_words

Compute the total length of a valid concatenation.

A valid substring must contain all words exactly once, so its total length equals word_len multiplied by the number of words.

Line 11 Standard

for w in words:

Iterate over each word in the words list.

Processing each word is necessary to build the frequency map that guides the sliding window validation.

Line 14 Standard

result = []

Initialize the result list to store valid starting indices.

All discovered starting positions of valid concatenations will be accumulated here and returned at the end.

Test Your Understanding

Why does the algorithm iterate over multiple offsets from 0 to word_len - 1 instead of just once from the start?

Because valid concatenations can start at any position aligned with the word length, iterating over all offsets ensures that all possible segmentations of the string into word-length chunks are considered, preventing missed matches due to misalignment.

Don't just read it. Drill it.

Reconstruct Substring with Concatenation of All Words from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Substring with Concatenation of All Words drill

or drill a free problem

3	`if not s or not words:`
4	`return []`
6	`word_len = len(words[0])`
7	`num_words = len(words)`
8	`total_len = word_len * num_words`
14	`result = []`

1	`class Solution:`
2	`def findSubstring(self, s: str, words: List[str]) -> List[int]:`
3	`if not s or not words:`
4	`return []`
5
6	`word_len = len(words[0])`
7	`num_words = len(words)`
8	`total_len = word_len * num_words`
9
10	`target = {}`
11	`for w in words:`
12	`target[w] = target.get(w, 0) + 1`
13
14	`result = []`
15
16	`for offset in range(word_len):`
17	`left = offset`
18	`window = {}`
19	`words_used = 0`
20
21	`for right in range(offset, len(s) - word_len + 1, word_len):`
22	`word = s[right:right + word_len]`
23
24	`if word in target:`
25	`window[word] = window.get(word, 0) + 1`
26	`words_used += 1`
27
28	`while window[word] > target[word]:`
29	`left_word = s[left:left + word_len]`
30	`window[left_word] -= 1`
31	`left += word_len`
32	`words_used -= 1`
33
34	`if words_used == num_words:`
35	`result.append(left)`
36
37	`else:`
38	`window.clear()`
39	`words_used = 0`
40	`left = right + word_len`
41
42	`return result`

Problem

Example

Approach

Solution

Step-by-Step Solution

Validate Inputs and Derive Fixed Word Parameters

Build Frequency Map of Target Words

Slide Window Over String in Word-Length Increments for Each Offset

Return All Valid Starting Indices

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.