# Very very straightforward python solution!

• When we saw this problem at the first sight, we can come up with `O(n*k)` solution easily. That is, for every position `s[i]`, we check that whether the `k` words is `s[i:i + k*length)]`. But unfortunately it got TLE.

And then we found that there are a lot of situations we calculated duplicately. If we use the result we have calculated, it would be faster. Based on above thought, we have solution below.

``````class Solution(object):
'''
Variables:
- window:    words queue appeared in order.
- localCout:     appeared times of each word in current window.

Processing:
- if current word is not in `words`, then we should re-start calculating from
next word.
- if current word is in `words` and it's appeared times beyond that in `words`,
then we should set the left boundary of `window` to position next to that in
which current word appeared the first time.
- if the length of window equals to that of `words`, then we get one pefect
position.
'''
def findSubstring(self, s, words):
n, m, r = len(words), len(words[0]) if words else 0, []
counter = collections.Counter(words)

for i in xrange(m):
localCout = collections.defaultdict(int)
window = collections.deque()

for j in xrange(i, len(s), m):
word = s[j:j + m]
if word in counter:
localCout[word] += 1
window.append(word)

while localCout[word] > counter[word]:
localCout[window.popleft()] -= 1

if len(window) == n:
r.append(j - (n - 1) * m)
else:
localCout.clear()
window.clear()
return r``````

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