Problem

# 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.
#
# For example, given:
# s: "barfoothefoobarman"
# words: ["foo", "bar"]
#
# You should return the indices: [0,9].
# (order does not matter).

AC

class Solution():
    def findSubstring(self, s, words):
        import collections
        dict  = collections.defaultdict(int)
        for w in words:
            dict[w] += 1
        res, l = [], len(words[0])
        for i in range(l):
            dict1, j = dict.copy(), i
            while j < len(s) - l + 1:
                dict1[s[j:j+l]] -= 1
                while dict1[s[j:j+l]] < 0:
                    dict1[s[i:i+l]] += 1
                    i += l
                j += l
                if (j-i) / l == len(words) :
                    res.append(i)
        return res


if __name__ == "__main__":
    assert Solution().findSubstring("barfoothefoobarman", ["foo", "bar"]) == [0, 9]