Step-by-step brute force & sliding window
Find all starting indices where a substring is a concatenation of every word in words (in any order, no gaps).
Step log — window movement & decisions
Test Cases
Classic example — two words, multiple valid windows.
Custom test case
Animation Controls
Complexity
O(n · w)
O(m)
Runs w passes (one per offset). Each pass is O(n/w) word operations. Avoids recomputing from scratch.
| 1 | function findSubstring(s, words) { |
| 2 | const wLen = words[0].length; |
| 3 | const wordMap = buildMap(words); |
| 4 | const result = []; |
| 5 | for (let i = 0; i < wLen; i++) { |
| 6 | let left = i, matched = 0; |
| 7 | const seen = {}; |
| 8 | for (let j = i; j <= s.length-wLen; j += wLen) { |
| 9 | const word = s.slice(j, j+wLen); |
| 10 | if (wordMap[word] !== undefined) { |
| 11 | seen[word] = (seen[word]||0) + 1; |
| 12 | matched++; |
| 13 | while (seen[word] > wordMap[word]) { |
| 14 | const lw = s.slice(left, left+wLen); |
| 15 | seen[lw]--; matched--; left += wLen; |
| 16 | } |
| 17 | if (matched === words.length) { |
| 18 | result.push(left); |
| 19 | seen[s.slice(left,left+wLen)]--; |
| 20 | matched--; left += wLen; |
| 21 | } |
| 22 | } else { |
| 23 | Object.keys(seen).forEach(k=>delete seen[k]); |
| 24 | matched = 0; left = j + wLen; |
| 25 | } |
| 26 | } |
| 27 | } |
| 28 | return result; |
| 29 | } |