@WKVictor nice solution, I tried a similar idea in python but python's heap does not have remove function.
Python Sliding Window Solution using Counter


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


@fatenaught
It is necessary, otherwiseCounter({'a': 0, 'b': 1})
will not equal toCounter({'b': 1})

Similar idea, but somewhat compact (obscure) code.
The main difference is that we counter letters in
p
as positive, letters ins
as negative.
So instead of deleting 0 counts, we can simply check allvalues
in the slidingCounter
def findAnagrams(self, s, p): cnt, lp, s = Counter(p), len(p), s+'' cnt.subtract(s[1] + s[:lp1]) # append '' to s, make s[1] valid when s='' return [i for i in xrange(len(s)lp+1) if cnt.update({s[i1+lp]: 1}) or # delete front letter by 1 when sliding forward cnt.update({s[i1 ]: 1}) or # add the letter in the back to counter not any(cnt.values())] # check all letters count to 0



@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[:np1]) # negative count for s for i in range(np1, ns): cnt.update({s[i]: 1}) # decrease window right i < np or cnt.update({s[inp]: 1}) # increase window left if not any(cnt.values()): # check all letters count 0 res.append(i(np1)) 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