30.py

'''
 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.
 Example 2:

 Input:
 s = "wordgoodstudentgoodword",
 words = ["word","student"]
 Output: []
'''

classSolution(object):
deffindSubstring(self, s, words):
"""
 :type s: str
 :type words: List[str]
 :rtype: List[int]
 """
ifnotstrornotwords:
return []

counts= {}
forwordinwords:
ifwordincounts:
counts[word] +=1
else:
counts[word] =1

result= []
n, numOfWords, fixLen=len(s), len(words),len(words[0])

forindexinrange(0, n-numOfWords*fixLen+1):
seen= {}

index_j=0
whileindex_j<numOfWords:
word=s[index+index_j*fixLen: index+ (index_j+1)*fixLen]
ifwordincounts:
ifwordinseen:
seen[word] +=1
else:
seen[word] =1

ifseen[word] >counts[word]:
break
else:
break
index_j+=1

ifindex_j==numOfWords:
result.append(index)

return

# Time: O(N^2)
# Space: O(N)