Substring with Concatenation of All Words

Hard~35 min

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.

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

Examples

Example 1
Input: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0, 9]
Explanation: The substring starting at index 0 is "barfoo" which is a concatenation of ["bar","foo"]. The substring starting at index 9 is "foobar" which is a concatenation of ["foo","bar"].
Example 2
Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output: []
Explanation: There is no concatenated substring.
Example 3
Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
Output: [6, 9, 12]
Explanation: The substrings starting at indices 6, 9, and 12 are "foobarthe", "barthefoo", and "thefoobar" respectively.

Constraints

  • 1 <= s.length <= 10^4
  • 1 <= words.length <= 5000
  • 1 <= words[i].length <= 30
  • s and words[i] consist of lowercase English letters
  • Expected time complexity: O(n*m)
Code
Ctrl+EnterRun|Ctrl+⇧+EnterSubmit
Output

Run your code to see results

Use Cmd+Enter to run