# code tpl

{%hackmd theme-dark %}

s = "cbaebabacd", p = "abc"

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

1. find all anagram in s
2. abc bca acb

0: cba
6: bac

-> [0, 6], [6, 0]

slide window

"[cba]ebabacd" -> tuple (1, 1, 1)26 # (a, b, c) -> same with p (1, 1, 1),

"c[bae]babacd" -c, +e tuple (1, 1, 0...)26 -> not match
"cb[aeb]abacd" -b, +b tuple (1, 1, 0...)26 -> not match

..
"cbaeba[bac]d", tuple (1, 1, 1...) -> same with p (1, 1, 1) , push 6

return ans [0, 6]

class Solution(object):
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        def getIdx(w):
            return ord(w) - 'a'
            
        pattern = [0]*26
        for w in p:
            pattern[getIdx(w)] += 1
        
        pattern = tuple(pattern) # (1, 1, 1)
        
        lenP = len(p)
        
        ans = []
        curPattern = [0]*26
        for w in s[:lenP]:
            curPattern[getIdx(w)] += 1
        
        if tuple(curPattern) == pattern:
            ans.append(0)
        
        "[(c-)ba](e+)babacd"
        "cbaebab[acd]" 
        for i in range(lenP, len(s)):
            newW = s[i] # e
            oldW = s[i-lenP] # c
            curPattern[getIdx(newW)] += 1
            curPattern[getIdx(oldW)] -= 1
            # (1, 1, 0...)
            if tuple(curPattern) == pattern:
                ans.append(i)
        return ans
        
        # N: num of S
        # M: num of P
        # TC: O(N)
        # SC: O(1)
        

###### tags: `mock interview` `面試`