Substring with Concatenation of All Words

Hard#30fixed size

You get a string s and a list of words, all of the same length. Find every index in s where all the words stand one after another, each used once, in any order. Our example: s = "stobeabeto", words = ["to", "be"] — the answer is [6, 1]: "beto" at 6 and "tobe" at 1.

30 Substring with Concatenation of All WordsWalkthrough · 1×

Example: s = "stobeabeto", words = ["to", "be"]. The words of the current pass are underlined; under s are need, seen and found.

0s1t2o3b4e5a6b7e8t9oneed—seen—found—
not reached yetwindowword coming inword going out, not neededleft the windowmade of the words

Every word has 2 letters: L = 2

01/75
restart · back · play · step
Speed
1function findSubstring(s, words):
2 L = len(words[0])
3 n = len(words)
4 need = count of each word in words
5 found = empty list
6 for offset from 0 to L - 1:
7 seen = empty map // missing keys: 0
8 for right from offset to len(s) - L, step L:
9 word = s[right .. right + L - 1]
10 seen[word] = seen[word] + 1
11 start = right - (n - 1) * L
12 if start - L >= offset:
13 old = s[start - L .. start - 1]
14 seen[old] = seen[old] - 1
15 if every w in need has seen[w] == need[w]:
16 add start to found
17 return found
state
L
2
n
–
need
–
found
–
offset
–
seen
–
right
–
word
–
start
–
old
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. An answer is n words in a row, so the window is a fixed n · L letters and moves a whole word at a time: one word comes in, one leaves, and seen is updated in O(1).
  2. Moving by a word only visits starts offset, offset + L, …, so the passes from 0 to L - 1 together try every start. Here "tobe" at 1 is seen only by the pass from 1.
  3. The window holds exactly n words, so if every word has its count from need, nothing else fits in: the window is the words in some order.

Complexity

Time O(|s| · (L + n)): the L passes together take about |s| steps, and each step cuts a word of L letters and checks need, which holds at most n words. Memory O(n · L + |s|): need holds the words, and seen keeps every word met in a pass, at 0 once it has left.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.