Question

You are given a string, s, and a list of words, words, that are all of the same length. 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.

Example 1:

Input:
  s = "barfoothefoobarman",
  words = ["foo","bar"]
Output: [0,9]
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.

Solution

Use a sliding window. At each position, find the occurrence for each word in words and compare it to that in words. If matches, then it is a valid solution.

from collections import Counter
class Solution:
    def findSubstring(self, s, words):
        """
        :type s: str
        :type words: List[str]
        :rtype: List[int]
        """
        cnt = len(words)
        if cnt == 0:
            return []
        size = len(words[0])

        if size == 0 or len(s) < cnt * size:
            return []

        hist = dict(Counter(words))
        res = []

        for idx in range(0, len(s) - cnt * size + 1):
            curr_hist = dict()
            for j in range(0, cnt):
                w = s[idx + j*size: idx + (j+1)*size]
                if w in hist:
                    if w in curr_hist:
                        curr_hist[w] += 1
                    else:
                        curr_hist[w] = 1
                else:
                    break
            if curr_hist == hist:
                res.append(idx)

        return res