Substring with Concatenation of All Words

Problem

Log scanners look for events that consist of a sequence of fixed-length machine codes - the codes can appear in any order, and each must appear exactly as many times as the spec lists. Given a string s and a list words of equal-length words, find all starting indices in s where some permutation of the concatenation of every word in words (duplicates included) begins.

Example 1:

Input: s = "barcatfoobar", words = ["cat", "foo"]
Output: [3]
Explanation: only the window at index 3 spells "catfoo" - both required words, adjacent, nothing extra.

Example 2:

Input: s = "catcatfoxfox", words = ["cat", "fox"]
Output: [3]
Explanation: the window at index 3 is "catfox" - one of each. Earlier "catcat" over-uses cat and cannot match.

Example 3:

Input: s = "aaaaaa", words = ["aa", "aa"]
Output: [0, 1, 2]
Explanation: every start 0-2 begins a run of two "aa" chunks; overlapping starts all qualify.

Constraints:

• 1 <= s.length <= 10^4
• 1 <= words.length <= 5000
• words[i].length == words[j].length for all pairs; 1 <= words[i].length
• words[i] consists of lowercase English letters.

Solution Breakdown

Approach - hash-counted sliding window hopping in word-sized steps, one pass per alignment offset.

Every word shares one length unit, so a valid concatenation is nothing more than a contiguous run of unit-sized chunks whose multiset equals the words list. That turns character matching into dictionary counting: hash words into a want map (multiplicity included - ["aa", "aa"] demands two aa chunks), then scan the string in chunk-sized steps. One catch: a window starting at index 1 visits different chunk boundaries than one starting at index 0, and stepping by unit visits only starts congruent to the initial offset. So the scan runs once per offset off in [0, unit) - together the passes cover every possible start exactly once, each pass moving in strides of unit.

Within a pass, right extends the window one chunk at a time. Three cases: a chunk outside want poisons every window containing it, so have clears and left jumps past it; a wanted chunk that pushes have[chunk] above its required count means the window over-uses it - evict chunks from the left until the excess is gone (the evictions preserve the earlier promise because only the duplicate's surplus is shed); and when the matched chunk count reaches len(words), the window is a full permutation - record left, then step left forward one chunk so the sweep can find the next window that reuses the tail. Trace "catcatfoxfox" with ["cat", "fox"], offset 0: chunk 0 cat lands, chunk 1 cat over-uses - evict chunk 0, left now 3; chunk 2 fox completes the window at left = 3 - the match [3]. Overlapping starts like "aaaaaa" with ["aa", "aa"] record 0 and 2 on offset 0 and 1 on offset 1 - all three windows are genuinely valid.

Edge cases - a string shorter than unit * len(words) returns empty (a cat can never host cat + dog); repeated words in the list are enforced by the counts, not by distinctness; outputs from different offset passes are sorted so indices come out ascending.

Complexity - O(n) chunk operations total: unit passes each stepping roughly n/unit chunks, and within a pass every chunk is appended, evicted, or skipped a constant number of times - the eviction while-loop's total work is bounded by the number of appends. O(words total length) space for the want map plus the window's have map. The brute-force alternative - re-verifying every start from scratch - is O(n * words * unit) and collapses on long repeated-word inputs.