30. Substring with Concatenation of All Words
You receive a string s and a list words in which every word has the same length L. A window of s is a full concatenation if it has length len(words) * L and can be chopped into consecutive L-sized pieces that use each entry of words exactly once — order does not matter, but a word that appears twice in the list must appear twice in the window.
Return every starting index of a full concatenation, sorted in increasing order. If there is none, the program should print -1.
For example, with words = ["ab", "cd", "ab"] the windows "abcdab", "ababcd", and "cdabab" all qualify, but "abcdcd" does not (wrong multiset) and "bcdaba" does not (pieces must align to the window's start).
Example 1:
Input: s = "barfoothefoobarman", words = ["foo", "bar"]
Output: [0, 9]
Explanation: Windows of length 6 starting at 0 ("barfoo") and 9 ("foobar") each split into the pieces {"bar", "foo"} — both words exactly once.
Example 2:
Input: s = "wordgoodgoodgoodbestword", words = ["word", "good", "best", "word"]
Output: []
Explanation: "word" must be used twice, but no 16-character window contains word, good, best, word with those exact multiplicities, so nothing matches.
Example 3:
Input: s = "barfoofoobarthefoobarman", words = ["bar", "foo", "the"]
Output: [6, 9, 12]
Explanation: Three overlapping 9-character windows work: "foobarthe" (6), "barthefoo" (9), and "thefoobar" (12).
Constraints:
- 1 ≤ s.length ≤ 10⁴
- 1 ≤ words.length ≤ 5000
- 1 ≤ words[i].length ≤ 30
- All words have the same length; words may repeat.
- s and every words[i] consist of lowercase English letters.
- Report the indices in increasing order; print -1 when there are none.
Hints:
Because every word has length L, a valid window never straddles word boundaries arbitrarily: from a given start, the window splits into fixed L-sized slots. Compare multisets with a hash map of counts.
Brute force: for each possible start, walk the window slot by slot, counting the words you see and aborting the moment a slot is not in the list or a count runs over. That is O(n · m · L) — correct, and fine for these limits.
For the linear approach, notice starts fall into L residue classes mod L. For each offset 0..L-1, slide a word-granular window: extend by one slot on the right, and while some word's count exceeds its quota, evict slots from the left. Each slot enters and leaves once.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s = "barfoothefoobarman", words = ["foo", "bar"]
Expected output: [0, 9]