hard

Substring with Concatenation of All Words

Find every starting point where a string is formed by joining all given words in any order.

1. Define the problem

Substring with Concatenation of All Words

Given a string s and words of equal length, return all starting indices of substrings that are a concatenation of every word exactly once in any order with no gaps. Slide word-sized windows per character offset.

Constraints

  • 1 ≤ s.length ≤ 104
  • 1 ≤ words.length ≤ 5000
  • 1 ≤ wordsi.length ≤ 30
  • s and wordsi consist of lowercase English letters
  • all wordsi have the same length

Example

Inputs = "barfoothefoobarman", words = ["foo","bar"]
Output[0,9]

Explanation s[0..5]="barfoo" and s[9..14]="foobar" are both concatenations of foo and bar.

2. Know the words first

In plain terms

Substring
A run of characters taken right out of the string as-is, next to each other in order — not letters picked out from anywhere, that's a different thing (a subsequence).
Concatenation
Joining pieces end to end with nothing in between, like sticking "foo" and "bar" together to get "foobar".
3. Visualize the solution

Word-aligned windows find every match

Word-aligned windows find every match
StatusMatch

Offset 0: words "bar"+"foo" match need → record index 0.

What happens in this step

window = [0, 5]  "barfoo"
need: {foo:1, bar:1}

add s[0:3]="bar" → window{bar:1}, count=1
add s[3:6]="foo" → window{bar:1,foo:1}, count=2 == numWords(2)
→ match! record start index 0.

After recording, the leftmost word "bar" is evicted (window[bar]: 1→0, count: 2→1) and left moves to 3, ready to keep sliding.
Step 1 of 4

Steps to visualize

  1. For each character offset, advance in steps of word length across s.
  2. Add each word chunk into a count map and compare against need.
  3. If a chunk is unknown, clear the window and jump past it.
  4. When a word is over-used, shrink left by one word until counts fit.
  5. When the window holds exactly all words, record the left index.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Word-aligned windows find every match
StatusMatch

Offset 0: words "bar"+"foo" match need → record index 0.

What happens in this step

window = [0, 5]  "barfoo"
need: {foo:1, bar:1}

add s[0:3]="bar" → window{bar:1}, count=1
add s[3:6]="foo" → window{bar:1,foo:1}, count=2 == numWords(2)
→ match! record start index 0.

After recording, the leftmost word "bar" is evicted (window[bar]: 1→0, count: 2→1) and left moves to 3, ready to keep sliding.
Step 1 of 4
5. Solution

Solution

solution.tsTypeScript
function findSubstring(s, words) {
  const result = [];
  if (s.length === 0 || words.length === 0) return result;

  const wordLen = words[0].length;
  const numWords = words.length;
  const windowLen = wordLen * numWords;
  if (s.length < windowLen) return result;

  const need = new Map();
  for (const w of words) need.set(w, (need.get(w) ?? 0) + 1);

  for (let offset = 0; offset < wordLen; offset++) {
    const window = new Map();
    let count = 0;
    let left = offset;

    for (let right = offset; right + wordLen <= s.length; right += wordLen) {
      const word = s.substring(right, right + wordLen);

      if (!need.has(word)) {
        window.clear();
        count = 0;
        left = right + wordLen;
        continue;
      }

      window.set(word, (window.get(word) ?? 0) + 1);
      count++;

      while (window.get(word) > need.get(word)) {
        const leftWord = s.substring(left, left + wordLen);
        window.set(leftWord, window.get(leftWord) - 1);
        count--;
        left += wordLen;
      }

      if (count === numWords) {
        result.push(left);
        const leftWord = s.substring(left, left + wordLen);
        window.set(leftWord, window.get(leftWord) - 1);
        count--;
        left += wordLen;
      }
    }
  }

  return result;
}
Time
O(n * wordLen)
Space
O(numWords * wordLen)
6. Test cases

Test cases

InputExpectedCovers
s = "barfoothefoobarman", words = ["foo","bar"][0,9]Docstring example
s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"][]No match exists
s = "", words = ["a"][]Empty s
s = "abc", words = [][]Empty words
s = "ab", words = ["abc"][]s shorter than concatenation length
s = "foobar", words = ["foo","bar"][0]Entire string is the only match
s = "barfoofoobarthefoobarfoobar", words = ["bar","foo","the"][6,9,12]Duplicate words / multiple matches
s = "word", words = ["word"][0]Single word equal to s
s = "aaaaaaaa", words = ["aa","aa","aa"][0,1,2]Overlapping windows with repeated words
s = "lingmindraboofooowingdingbarrwingmonkeypoundcake", words = ["fooo","barr","wing","ding","wing"][13]Larger hand-verified case

Keep reading