DSA problem
Substring with Concatenation of All Words
You are given a string s and an array of strings words. All the strings of words are of the same length.
A concatenated substring in s is a substring that contains all the strings of any permutation of words concatenated.
- For example, if
words = ["ab","cd","ef"], then"abcdef","abefcd","cdabef","cdefab","efabcd", and"efcdab"are all concatenated strings."acdbef"is not a concatenated substring because it is not the concatenation of any permutation ofwords.
Return the starting indices of all the concatenated substrings in s. You can return the answer in any order.
Because every word has the same length L and there are m words, every valid concatenated substring has the fixed total length L * m. By running a sliding window in L separate offset phases, each phase advances word-by-word, letting us reuse word counts in linear time.
Examples
Example 1
Input:
s = "barfoothefoobarman", words = ["foo","bar"]Output:
[0,9]Explanation: The substring starting at index 0 is "barfoo", a concatenation of ["bar","foo"]. The substring starting at index 9 is "foobar", a concatenation of ["foo","bar"]. The output order does not matter.
Example 2
Input:
s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]Output:
[]Explanation: There is no concatenated substring because "word" must appear twice but the only such window does not exist contiguously.
Example 3
Input:
s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]Output:
[6,9,12]Explanation: Index 6 -> "foobarthe", index 9 -> "barthefoo", index 12 -> "thefoobar" are all valid permutations of the three words.
Constraints
- 1 <= s.length <= 10^4
- 1 <= words.length <= 5000
- 1 <= words[i].length <= 30
- s and words[i] consist of lowercase English letters.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.