Approach: use dictionaries to check if two strings are anagrams.
p_dict is fixed, while s_dict is changing based on the moving window.
Construct s_dict based on substrings of s, each with length = len(p).
More details on how to construct s_dict below
This solution has O(n) in time complexity and O(m) in space complexity, where n is len(s) and m is len(p).
# Make sure to include from collections import Counter output =  p_dict = Counter(p) s_dict = Counter(s[:len(p)-1]) for i in range(len(p)-1, len(s)): s_dict[s[i]] += 1 # Put/update new char (new character in the moving window) to s_dict. idx = i-len(p) + 1 # Index of the first char in the window. first = s[idx] # First char in the window. if p_dict == s_dict: # If two dictionaries are the same, we find an anagram output.append(idx) if s_dict[first] == 1: # If s_dict[first] is 1, which means 'first' (first char in the window) del s_dict[first] # will disapear in the next window else: s_dict[first] -= 1 # Otherwise, reduce its appearance by 1 return output