# Leetcode 438. Find All Anagrams in a String

## 題解

### Hash Map + Slide Window

使用 Hash Map 比較字串組合的數量，這樣就不需要做 Back Tracking 了

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        # Time complexity: O(s)
        # Space Complexity: O(length of a-z)
        s_len = len(s)
        p_len = len(p)
        s_count = {}
        p_count = {}
        output = []

        if p_len > s_len:
            return output
        
        for i in range(ord('a'),ord('z') + 1):
            s_count[chr(i)] = 0
            p_count[chr(i)] = 0
        
        for i in range(0, p_len):
            s_count[s[i]] += 1
            p_count[p[i]] += 1
        
        if s_count == p_count:
            output.append(0)
        
        left = 0
        right = p_len - 1
        while right < s_len - 1:
            s_count[s[left]] -= 1
            left += 1
            right += 1
            s_count[s[right]] += 1
            if s_count == p_count:
                output.append(left)
        return output