We need to find every starting index in s where a substring of length words.length * wordLength is exactly a concatenation of all words in some order. The order doesn't matter, so we are looking for positions where the substring can be split into word-sized chunks that form the same multiset as words.

Checking permutations is unnecessary. Since order does not matter, we only need to verify that the frequency of each word-chunk matches the frequency of words in the array. Two multisets are equal if and only if every element appears the same number of times in both.

words can contain duplicates (like ["word","good","best","word"] in Example 2), so a simple set is not enough. We need a frequency map.

Key Constraints:

Intuition

For every possible starting position in s, extract a substring of the right total length, split it into word-sized chunks, and check whether those chunks form the same multiset as words.

Build a frequency map of words once upfront. Then for each starting index i, extract m consecutive chunks of length w from position i, build a frequency map of those chunks, and compare the two maps. If they match, i is a valid starting index. To avoid building the full map when it cannot match, increment the count of each chunk as it is read and stop early the moment any chunk's count exceeds its target count (which also covers chunks that are not in the target at all, since their target count is zero).

Algorithm

Example Walkthrough

Take s = "barfoothefoobarman", words = ["foo","bar"]. Here w = 3, m = 2, totalLen = 6, and target = {foo: 1, bar: 1}. Valid starting positions run from 0 to 18 - 6 = 12.

The result is [0, 9], matching the expected output.

Code

The bottleneck is that we rebuild the seen frequency map from scratch at every starting position. Moving from position i to position i + w, the two windows share m - 1 of the same word chunks, but this approach discards that overlap and starts over. The next approach reuses it by sliding a fixed-size window one chunk at a time.

Intuition

Since every word has the same length w, the string s decomposes into word-sized chunks, but the decomposition depends on where the alignment starts. Starting at index 0 gives chunks s[0..w-1], s[w..2w-1], s[2w..3w-1], and so on. Starting at index 1 shifts every chunk by one character. There are exactly w distinct alignments, one for each starting offset 0, 1, 2, ..., w-1, and every possible window start falls into exactly one alignment.

Within one alignment, the chunks form a fixed sequence of non-overlapping words. That lets us slide a window of exactly m consecutive chunks one chunk at a time: add the new chunk on the right, and once the window holds more than m chunks, remove the leftmost one. A window whose chunk frequencies match target is a valid concatenation.

Comparing the full seen and target maps at every step would cost O(distinct words) per step. Instead, maintain a single integer matchCount that tracks how many distinct words currently satisfy seen[word] == target[word]. The window is valid exactly when matchCount equals the number of distinct words in target, and matchCount updates in O(1) whenever a word enters or leaves the window.

Algorithm

Example Walkthrough

Take s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]. Here w = 3, m = 3, totalLen = 9, target = {bar: 1, foo: 1, the: 1}, and distinctWords = 3. The expected answer is [6, 9, 12]. All three indices are multiples of 3, so offset k = 0 finds all of them and offsets 1 and 2 contribute nothing. Trace offset 0, whose chunks are bar foo foo bar the foo bar man. Each step adds the chunk at right, then shrinks from left once the window holds more than m words.

The window then reaches the end of the string, offsets 1 and 2 add nothing, and the result is [6, 9, 12].

Code