# Python Sliding Window Solution using Counter

• @WKVictor nice solution, I tried a similar idea in python but python's heap does not have remove function.

• @fatenaught yes, otherwise, a key with value 0 will be left. This key should be deleted to ensure the cs can equal with cp.

• @weijuemin Notice the beginning of his code, from collections import Counter.

• @fatenaught
It is necessary, otherwise `Counter({'a': 0, 'b': 1})` will not equal to `Counter({'b': 1})`

• Similar idea, but somewhat compact (obscure) code.

The main difference is that we counter letters in `p` as positive, letters in `s` as negative.
So instead of deleting 0 counts, we can simply check all `values` in the sliding `Counter`

``````def findAnagrams(self, s, p):
cnt, lp, s = Counter(p), len(p), s+'|'
cnt.subtract(s[-1] + s[:lp-1])                                            # append '|' to s, make s[-1] valid when s=''
return [i for i in xrange(len(s)-lp+1) if cnt.update({s[i-1+lp]: -1}) or  # delete front letter by 1 when sliding forward
cnt.update({s[i-1   ]:  1}) or  # add the letter in the back to counter
not any(cnt.values())]          # check all letters count to 0

``````

• @waigx gotcha, thx.

• @hw1472 thanks.

• @waigx Very smart solution using pos/neg counts and Counter.update(). I modified your code a little to make it more straightforward.

``````class Solution2(object):
def findAnagrams(self, s, p):
"""
:type s: str
:type p: str
:rtype: List[int]
"""
ns, np, res = len(s), len(p), []
cnt = Counter(p)  # positive count for p
cnt.subtract(s[:np-1])  # negative count for s
for i in range(np-1, ns):
cnt.update({s[i]: -1})  # decrease window right
i < np or cnt.update({s[i-np]: 1})  # increase window left
if not any(cnt.values()):  # check all letters count 0
res.append(i-(np-1))
return res
``````

• @algowl I don't think you need to check i < np in the for loop. The following should work.

``````class Solution(object):
def findAnagrams(self, s, p):
"""
:type s: str
:type p: str
:rtype: List[int]
"""
res = []
cnt = Counter(p)
cnt.subtract(s[:len(p) - 1])
for i in range(len(p) - 1, len(s)):
cnt.update({s[i]: -1})
if not any(cnt.values()):
res.append(i - len(p) + 1)
cnt.update({s[i - len(p) + 1]: 1})
return res
``````

• This post is deleted!

• if not d: ans.append(i-np+1)
i guess here is some bug in the code
if not d: ans.append(i-np+1)
should be
if not d: ans.append(i-np)

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