# 99ms Python O(kmn) Solution

• The idea comes from [https://leetcode.com/discuss/20151/an-o-n-solution-with-detailed-explanation]

Using a counter and a sliding window, we push the window from left to right, counting the number of valid words in the window. When the number of a word in the window is more than the times it appears in words or we meet a invalid word, push the window.

``````class Solution:
# @param {string} s
# @param {string[]} words
# @return {integer[]}
def findSubstring(self, s, words):
if len(words) == 0:
return []
# initialize d, l, ans
l = len(words[0])
d = {}
for w in words:
if w in d:
d[w] += 1
else:
d[w] = 1
i = 0
ans = []

# sliding window(s)
for k in range(l):
left = k
subd = {}
count = 0
for j in xrange(k, len(s)-l+1, l):
tword = s[j:j+l]
# valid word
if tword in d:
if tword in subd:
subd[tword] += 1
else:
subd[tword] = 1
count += 1
while subd[tword] > d[tword]:
subd[s[left:left+l]] -= 1
left += l
count -= 1
if count == len(words):
ans.append(left)
# not valid
else:
left = j + l
subd = {}
count = 0

return ans
``````

Assuming we have k words in words, and there are m substrings in the string, the complexity is O(kmn) because we need to adjust the window when more valid words are found.

This solution runs 99ms on OJ.

• There is a built-in Python Counter that provides this functionality:

https://docs.python.org/2/library/collections.html#collections.Counter

Thanks for the solution!

• for k in range(l): can be xrange
count can be derived from left and j
code can be simplified a bit by using defaultdict
the condition of the while loop can be just comparing the strings (between the head to the current at j), should be a bit cheaper than check the count.

• I felt that above post could have a little more explanation. I had some difficulty understanding the above solution so I am adding this. It is based on the above approach only but has little detailed comments and uses Counter and defaultdict for ease.

``````        from collections import Counter
from collections import defaultdict
c = Counter(words)
m = len(words)
n = len(words[0])
ret = []
total_length = m * n

#Loop over word length
for k in xrange(n):
left = k
subd = defaultdict(int)
count = 0
#Loop over the string
for j in xrange(k, len(s) - n + 1, n):
#Get a word from observed substring
word = s[j:j+n]
#check if it is a valid word
if word in c:
subd[word] += 1
count += 1
##Shift the window as long as we have encountered more number of a word than is needed
##Note that we can shift the window by word length directly as the outer loop is there to
##make sure that anything is not missed out
##This solution will give indices out of order by OJ accepts it.
while subd[word] > c[word]:
subd[s[left:left+n]] -= 1
left += n
count -= 1
##Count will be equal to m only when we all the words are read the exact number of times needed
if count == m:
ret.append(left)
#If is not a valid word then just skip over the current word (Don't worry about the middle characters
##outer loop will take care of it)
else:
left = j + n
subd = defaultdict(int)
count = 0

return ret``````

• @Anavil Why not just use counter instead of defaultdict?

• very nice code.
I think your code is better than shichaotan's

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.