Substring with Concatenation of All Words

The key idea

Every word has the SAME length L, so a valid window is a fixed k*L characters that splits cleanly into k words on an L-aligned grid. Slide a window over the L-aligned word sequence and keep a count map; the window is an answer exactly when its word-counts equal the needed multiset.

Problem

You are given a string s and an array of strings words. All the strings in words are of the same length.

A concatenated substring in s is a substring that contains all the strings of words concatenated in any order, with no characters in between. For example, if words is ["ab","cd","ef"], then "abcdef", "abefcd", "cdabef", "cdefab", "efabcd", and "efcdab" are all concatenated substrings, while "acdbef" is not.

Return an array of the starting indices of all concatenated substrings in s. You can return the answer in any order.

Note that the same string may appear multiple times in words, and a valid window must use each of those copies the same number of times.

Constraints

1 <= s.length <= 10^4
1 <= words.length <= 5000
1 <= words[i].length <= 30
s and words[i] consist of lowercase English letters.

Examples

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

Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"] Output: []

Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"] Output: [6,9,12]

Complexity

Time: O(n * L) Space: O(m * L)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →