# 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).
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]