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 string is a string that exactly 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 string because it is not the concatenation of any permutation ofwords.
Return an array of the starting indices of all the concatenated substrings in s. You can return the answer in any order.
Example 1
Input
s = "barfoothefoobarman", words = ["foo","bar"]Output
[0,9]The substrings starting at indices 0 and 9 are "barfoo" and "foobar", each containing "bar" and "foo" exactly once.
Example 2
Input
s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]Output
[]No substring can be formed by concatenating the given words with the required frequencies.
Constraints
- 1 <= s.length <= 10^4
- 1 <= words.length <= 5000
- 1 <= words[i].length <= 30
- s and words[i] consist of lowercase English letters.