Substring with Concatenation of All Words [Hard] — Multi-Start Window

Problem Statement

Given string s and array words (all same length), find all starting indices of substrings that are concatenations of all words in any order.

Input: s="barfoothefoobarman", words=["foo","bar"]
Output: [0,9]

Intuition

Fixed window of size total_len = word_len × word_count. Try each starting offset 0..word_len-1 separately (word-aligned starts). Slide by one word at a time, using two word-frequency maps.

Solutions

Python

from collections import Counter

def findSubstring(s: str, words: list[str]) -> list[int]:
    if not s or not words: return []
    wlen = len(words[0]); wcount = len(words)
    total = wlen * wcount
    need = Counter(words)
    res = []
    for start in range(wlen):
        have = Counter()
        formed = 0
        left = start
        for right in range(start, len(s)-wlen+1, wlen):
            w = s[right:right+wlen]
            if w in need:
                have[w] += 1
                if have[w] == need[w]: formed += 1
                while have[w] > need[w]:
                    lw = s[left:left+wlen]
                    if lw in need:
                        if have[lw] == need[lw]: formed -= 1
                        have[lw] -= 1
                    left += wlen
                if formed == len(need) and right-left+wlen == total:
                    res.append(left)
            else:
                have.clear(); formed = 0; left = right+wlen
    return res

Complexity

Time: O(n × word_len) — word_len passes of O(n/word_len) each
Space: O(word_count)