Substring with Concatenation of All Words

Hash TableSliding WindowString

You are given a string s and a list of non-empty words words. All words in the list 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 ascending order.

Example 1

Input

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

Output

[0,9]

Explanation. The substrings starting at index 0 and 9 are 'barfoo' and 'foobar' respectively, which are concatenations of 'foo' and 'bar'.

Example 2

Input

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

Output

[8]

Explanation. The substrings starting at index 8 is 'goodgoodgoodbest' which consists exactly of the words 'word', 'good', 'best', 'good' in some order.

Example 3

Input

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

Output

[6,9,12]

Explanation. Substrings starting at indexes 6, 9, 12 are 'foobarthe', 'barthefoo', 'thefoobar' which are concatenations of 'bar', 'foo', 'the'.

Example 4

Input

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

Output

[]

Explanation. There is no substring that is a concatenation of 'word', 'good', 'best', 'word' without any intervening characters.

Follow-up: Can you improve the time complexity of your solution to handle `words` array with many frequent duplicates?

Constraints:

1. `1 <= s.length <= 10^4`\n2. `1 <= words.length <= 5000`\n3. `1 <= words[i].length <= 30`\n4. All the characters in `s` and `words[i]` are lowercase English letters.

Views: 3