Skip to main content

85. Substring with Concatenation of All Words

hardAsked at Plaid

Find all starting indices of substrings that are concatenations of every word in a given list (each used exactly once, any order). Plaid asks this as a multi-token sliding-window problem — exactly the shape they use to find required-feature sequences in a webhook batch.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Plaid loops.

  • LeetCode Discuss (2026)— Plaid SWE III hard sliding-window.
  • Glassdoor (2025)— Plaid backend onsite.

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 substring in s is a substring that contains all the strings of any permutation of words concatenated. Return the starting indices of all the concatenated substrings in s.

Constraints

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

Examples

Example 1

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

Example 2

Input
s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output
[]

Approaches

1. Try every starting position

For each i, scan k * wordLen characters and check.

Time
O(n * k * w)
Space
O(k * w)
// Triple-nested. Mention as starting point.

Tradeoff: Works but slow for n=10^4.

2. Sliding window with word-count map

For each offset 0..wordLen-1, slide a window of wordLen-aligned positions. Maintain a count map; expand right with current word, shrink left if count exceeded or non-matching word.

Time
O(n * w)
Space
O(k * w)
function findSubstring(s, words) {
  const k = words.length, w = words[0].length;
  const need = new Map();
  for (const wd of words) need.set(wd, (need.get(wd) || 0) + 1);
  const out = [];
  for (let off = 0; off < w; off++) {
    let left = off, count = 0;
    const window = new Map();
    for (let right = off; right + w <= s.length; right += w) {
      const wd = s.slice(right, right + w);
      if (!need.has(wd)) {
        window.clear();
        count = 0;
        left = right + w;
        continue;
      }
      window.set(wd, (window.get(wd) || 0) + 1);
      count++;
      while (window.get(wd) > need.get(wd)) {
        const lw = s.slice(left, left + w);
        window.set(lw, window.get(lw) - 1);
        count--;
        left += w;
      }
      if (count === k) out.push(left);
    }
  }
  return out;
}

Tradeoff: n * w. The 'iterate over offsets' is the key — each offset gives a distinct alignment to the word boundary.

Plaid-specific tips

Plaid grades this on whether you batch by word-length offsets. Bonus signal: explicitly mention the 'shrink while over-count' invariant — it's the same shape as LC 76. Connect to feature-sequence matching across a webhook batch.

Common mistakes

  • Iterating only at index 0..n - k*w — misses the offset variants.
  • Comparing entire count maps inside the loop — quadratic.
  • Resetting the window on every non-match without advancing left.

Follow-up questions

An interviewer at Plaid may pivot to one of these next:

  • Words of varying lengths.
  • Allow at most one missing word.
  • Generalize to multi-key matches over streaming data.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why iterate over offsets 0..wordLen?

Each starting position must be wordLen-aligned. There are wordLen possible alignments; we sweep each independently.

When does this match LC 76?

Both are sliding window with a count map and a 'shrink while over-count' rule. LC 30 just operates on word units instead of characters.

Practice these live with InterviewChamp.AI

Drill Substring with Concatenation of All Words and other Plaid interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →