438. Find All Anagrams in a String

two_pointer, O(n) time.
简化版的同向双指针, 像 Minimum Window Substring.
window 大小固定, 总是一进一出, 像 strStr II - rolling hash.
.

from collections import defaultdict
class Solution:
    def findAnagrams(self, s, p):
        sn, pn = len(s), len(p)
        if pn > sn:
            return []
        r = l = 0
        p_cnt = defaultdict(int)
        s_cnt = defaultdict(int)
        for c in p:
            p_cnt[c] += 1
        tot = 0
        res = []
        for i in range(pn):
            c = s[i]
            if c in p_cnt:
                if s_cnt[c] < p_cnt[c]:
                    tot += 1
                s_cnt[c] += 1

        for i in range(pn, sn + 1):
            if tot == pn:
                res.append(i - pn)
            if i == sn:
                break
            old = s[i - pn]
            new = s[i]
            if old in p_cnt:
                if 0 < s_cnt[old] <= p_cnt[old]:
                    tot -=1
                s_cnt[old] -= 1
            if new in p_cnt:
                if s_cnt[new] < p_cnt[new]:
                    tot += 1
                s_cnt[new] += 1

        return res

s, p = \
"bpaa", \
"aa"

s = "abddabaff"; p = "ab"

o = Solution()
ans = o.findAnagrams(s, p)
print(ans)