Substring with Concatenation of All Words

Hash TableSliding WindowString

You are given a string s and an array of strings words. All the strings in words are of the same length. Find all the starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters. Return the indices in the ascending order.

Example 1

Input

[
  "barfoothefoobarman",
  [
    "foo",
    "bar"
  ]
]

Output

[0, 9]

Explanation. The substring starting at index 0 is 'barfoo' which is a concatenation of 'bar' and 'foo'. Similarly, the substring starting at index 9 is 'foobar' which is a concatenation of 'foo' and 'bar'.

Example 2

Input

[
  "wordgoodgoodgoodbestword",
  [
    "word",
    "good",
    "best",
    "word"
  ]
]

Output

[]

Explanation. There's no substring matching the concatenation pattern exactly once with no intervening characters.

Example 3

Input

[
  "barfoofoobarthefoobarman",
  [
    "bar",
    "foo",
    "the"
  ]
]

Output

[6, 9, 12]

Explanation. The substrings 'foobarthe', 'barthefoo', 'foobarthe' at indices 6, 9, and 12 respectively, match the pattern.

Follow-up: Can you optimize the solution by employing more efficient data structures or utilizing properties of string and array for faster computation?

Constraints:

- 1 <= s.length <= 104\n- 1 <= words.length <= 5000\n- 1 <= words[i].length <= 30\n- All characters in `s` and `words[i]` are lowercase English letters.

Views: 2