Skip to main content

94. Substring with Concatenation of All Words

hardAsked at Datadog

Find all starting indices of substrings that are a concatenation of each word exactly once. Datadog asks this for the hash-based sliding window — same shape as multi-tag-pattern detection on a log stream.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite — log-pattern detection analog.

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. Hash count check per start position

For each i, slice s[i..i+L] into words.length chunks; count-match against words.

Time
O(N * M * L)
Space
O(M)
// For each i, split substring into words; map count; compare.

Tradeoff: Cubic-ish. Works but slow.

2. Sliding window per offset (optimal)

For each of the L word-length offsets, sliding window of M words. Track count map of words in window vs target.

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

Tradeoff: O(N * L). Datadog-canonical pattern when 'all words' are fixed-length tokens.

Datadog-specific tips

Datadog grades on the per-offset sliding window. The L offsets ensure every word boundary is covered. Articulate why a SINGLE sliding window over chars would miss alignment.

Common mistakes

  • Sliding by 1 char instead of L — exponentially redundant.
  • Forgetting to clear the window on a non-matching word — propagates stale counts.
  • Comparing whole windows via JSON.stringify — slow.

Follow-up questions

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

  • Minimum Window Substring (LC 76) — variable-length tokens.
  • Datadog-style: detect multi-tag patterns in a log stream.
  • Concatenated Words (LC 472) — different problem.

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 L offsets?

A valid match starts at any char position. By fixing the offset modulo L, we align all word boundaries; together L offsets cover every position.

What's the count variable for?

Tracks how many target words are currently in the window. When count == M, we have a full match.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →