30. Substring with Concatenation of All Words
Problem Statement
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.
Example 1:
Example 2:
Example 3:
Constraints:
1 <= s.length <= 104
1 <= words.length <= 5000
1 <= words[i].length <= 30
s
andwords[i]
consist of lowercase English letters.
Intuition
Links
Video Links
Approach 1:
Approach 2:
Approach 3:
Approach 4:
Similar Problems
Last updated