‹ DS&A interview · Socratic
DSA · Sliding Window · #170

Substring with Concatenation of All Words

Module 71 · difficulty 4/5·⏱ 30:00starts on first keystroke

You are given a string `s` and an array of strings `words` where **all** strings in `words` have the **same length**. A *concatenated substring* is a substring of `s` that is formed by concatenating every string in `words` exactly once, in **any order**, with no characters in between. Implement `findSubstring(s, words)` that returns an array of the **starting indices** of every concatenated substring in `s`. The order of the returned indices does not matter.

Examples
  • s = "barfoothefoobarman", words = ["foo","bar"] → [0,9] — At index 0 "barfoo" = bar+foo; at index 9 "foobar" = foo+bar. Both use each word exactly once.
  • s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"] → [] — No window contains "word" twice plus "good" and "best".
  • s = "barfoofoobarthefoobarman", words = ["bar","foo","the"] → [6,9,12]
Constraints
  • · 1 <= s.length <= 10^4
  • · 1 <= words.length <= 5000
  • · 1 <= words[i].length <= 30
  • · s and words[i] consist of lowercase English letters.
  • · All words[i] have the same length.
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.