Skip to main content

85. Substring with Concatenation of All Words

hardAsked at Salesforce

Find all starting indices where a concatenation of all given words appears. Salesforce uses this as an advanced sliding-window with multiplicity tracking.

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

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

  • Glassdoor (2026-Q1)— Salesforce uses similar patterns in their multi-token search ranking.
  • LeetCode Discuss (2025)— Hard variant of substring matching.

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
  • 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. Brute force all starting indices

At each i, try matching exactly k words from i; advance by k * wordLen.

Time
O(n * k * w)
Space
O(k)
function findSubstring(s, words) {
  const result = [], wordLen = words[0].length, totalLen = wordLen * words.length;
  const wordCount = new Map();
  for (const w of words) wordCount.set(w, (wordCount.get(w) || 0) + 1);
  for (let i = 0; i + totalLen <= s.length; i++) {
    const seen = new Map();
    let j = 0;
    for (; j < words.length; j++) {
      const w = s.slice(i + j * wordLen, i + (j + 1) * wordLen);
      if (!wordCount.has(w)) break;
      seen.set(w, (seen.get(w) || 0) + 1);
      if (seen.get(w) > wordCount.get(w)) break;
    }
    if (j === words.length) result.push(i);
  }
  return result;
}

Tradeoff: Acceptable but O(n * k * w). Sliding-window version is faster.

2. Sliding window for each starting offset

For each offset (0..wordLen-1), slide a window of wordLen-sized chunks. Maintain a word-count map; shrink left when invalid.

Time
O(n * w)
Space
O(k)
// Complex — show outline only; full code is ~40 lines.

Tradeoff: Faster but trickier. Salesforce will accept the brute force for this hard problem.

Salesforce-specific tips

Salesforce treats this as a stretch problem — they value a clean brute-force more than an attempted-and-broken sliding window. They use similar multi-token matching in their search ranking pipeline. Bonus signal: discuss why the words-of-equal-length constraint enables the chunked iteration trick.

Common mistakes

  • Treating words as a set (ignores multiplicity) — fails on duplicate words.
  • Off-by-one on totalLen — must use wordLen * words.length.
  • Sliding the window by 1 instead of wordLen — wastes work.

Follow-up questions

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

  • Minimum Window Substring (LC 76) — variable-length, single string target.
  • Find All Anagrams in a String (LC 438).
  • What if words have variable length?

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 all words equal length?

It enables chunked iteration — every word starts at a position i mod wordLen. Without this, the search space explodes.

Sliding window with starting offsets?

Each offset 0..wordLen-1 defines an independent alignment. The total work across all offsets is O(n).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →