You are given a string, s, and a list of words, words, that are all of the same lengths. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.
Input: s = “barfoothefoobarman”, words = [“foo”,”bar”]
Explanation: Substrings starting at index 0 and 9 are “barfoor” and “foobar” respectively. The output order does not matter, returning [9,0] is fine too.
First, this kind of substring must is anagrams of words too. So you can use function findAnagrams of problem 438 first.
Then we check in the returned list to make sure each word in words exactly once and without any intervening characters.
This is the code:
Running time is 94ms.
Code download address: https://github.com/tinyfool/leetcode/tree/master/src/p0030
Want to know details of the sliding window algorithm, check my post: The Sliding Window Algorithm for string and array.