Problem statement

https://binarysearch.com/problems/Anagram-Substrings/

Solution

Equal to Leetcode 0438 Find All Anagrams in a String

Complexity

Overall complexity is O(n + m), where n and m are sizes of strings s and p. Space is O(26).

Code

class Solution:
    def solve(self, p, s):
        dict_p, dict_s = Counter(p), defaultdict(int)
        num_to_correct, ans = len(dict_p), 0
            
        for i in range(0, len(s)):  
            new_s = s[i]
            dict_s[new_s] += 1
            if dict_s[new_s] == dict_p[new_s]:
                num_to_correct -= 1
            if dict_s[new_s] == dict_p[new_s] + 1:
                num_to_correct += 1
                
            if i >= len(p):
                old_s = s[i - len(p)]
                dict_s[old_s] -= 1
                if dict_s[old_s] == dict_p[old_s] - 1:
                    num_to_correct += 1
                if dict_s[old_s] == dict_p[old_s]:
                    num_to_correct -= 1
                                
            if num_to_correct == 0: ans += 1         
                    
        return ans