Leetcode 438 -- Find All Anagrams in a String.py

# Leetcode 438: Find All Anagrams in a String
# https://leetcode.com/problems/find-all-anagrams-in-a-string/

from collections import Counter

class Solution(object):
    def findAnagrams(self, s, p):
        # Method 1: Fixed Sliding Window
        target = Counter(p)
        window = Counter()
        result = list() # to place start indices of p that work
        left = 0

        for right, value in enumerate(s):
            # add the current character into the freq map
            window[value] += 1
            # adjust the window size if it's too big
            if right - left + 1 > len(p):
                # moving the left most character out of the hashmap
                window[s[left]] -= 1
                if window[s[left]] == 0:
                    del window[s[left]]
                # move left index 1 to the right
                left += 1
            # if the window matches what we are trying to find, and its the right length
            if right - left + 1 == len(p) and window == target:
                # add starting index to result
                result.append(left)
        return result

        #time complexity: O(N)
        #space complexity: O(N+m) or just O(N)

#time complexity: O(N)
#space complexity: O(N)