85. Substring with Concatenation of All Words
hardAsked at SalesforceFind all starting indices where a concatenation of all given words appears. Salesforce uses this as an advanced sliding-window with multiplicity tracking.
By Sam K., 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^41 <= words.length <= 50001 <= words[i].length <= 30s and words[i] consist of lowercase English letters.
Examples
Example 1
s = "barfoothefoobarman", words = ["foo","bar"][0,9]Example 2
s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"][]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.
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).