Skip to main content

85. Substring with Concatenation of All Words

hardAsked at Snowflake

Find all starting indices where a substring is a concatenation of every word exactly once. Snowflake asks this for multi-key sliding-window mastery — relevant to multi-column join-key matching in streaming joins.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2025-Q4)— Snowflake execution-engine team uses this in onsites.
  • LeetCode Discuss (2025-09)— Reported at Snowflake SDE-II screens.

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. You can return the answer in any order.

Constraints

  • 1 <= s.length <= 10^4
  • 1 <= words.length <= 5000
  • 1 <= words[i].length <= 30
  • All strings in words are of the same length.
  • s and words[i] 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 start index, check word match

For each start i, count words within s[i:i+wordLen*wordCount].

Time
O(n * m * k)
Space
O(m)
// outline only — for each start, build a counter of words present.

Tradeoff: Works but rechecks fully for each shift.

2. Sliding window over word boundaries (optimal)

For each offset in [0, wordLen), slide a window of wordCount words. Maintain a counter of words seen; on overflow or unknown word, shrink left.

Time
O(n * wordLen)
Space
O(m)
function findSubstring(s, words) {
  const wordLen = words[0].length;
  const wordCount = words.length;
  const windowLen = wordLen * wordCount;
  const need = new Map();
  for (const w of words) need.set(w, (need.get(w) || 0) + 1);
  const result = [];
  for (let offset = 0; offset < wordLen; offset++) {
    let left = offset;
    let count = 0;
    const have = new Map();
    for (let right = offset; right + wordLen <= s.length; right += wordLen) {
      const w = s.slice(right, right + wordLen);
      if (!need.has(w)) {
        have.clear();
        count = 0;
        left = right + wordLen;
        continue;
      }
      have.set(w, (have.get(w) || 0) + 1);
      count++;
      while (have.get(w) > need.get(w)) {
        const leftWord = s.slice(left, left + wordLen);
        have.set(leftWord, have.get(leftWord) - 1);
        count--;
        left += wordLen;
      }
      if (count === wordCount) {
        result.push(left);
        const leftWord = s.slice(left, left + wordLen);
        have.set(leftWord, have.get(leftWord) - 1);
        count--;
        left += wordLen;
      }
    }
  }
  return result;
}

Tradeoff: Linear over offsets, sliding window per offset. Cleanly handles overflowing words by shrinking left.

Snowflake-specific tips

Snowflake interviewers want the offset-loop + sliding-window pattern. Bonus signal: connect to multi-column join-key matching in streaming joins — maintaining counts of unmatched keys is the same shape.

Common mistakes

  • Trying to slide one character at a time — wasteful, since matches align on wordLen boundaries.
  • Forgetting to reset state when an unknown word is encountered.
  • Overcounting matches when overlapping windows produce the same index.

Follow-up questions

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

  • Allow duplicate words (already handled).
  • Allow approximate matches with bounded edit distance.
  • How does Snowflake match multi-key joins on streams?

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 offset in [0, wordLen)?

Valid starts lie on multiples of wordLen relative to each offset. Iterating wordLen offsets covers all possible alignments.

How does this connect to streaming joins?

When joining a stream on (col1, col2, col3), the executor maintains a count of unsatisfied composite keys. The shrink-on-overflow pattern is identical.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →