Leetcode 0438 Find All Anagrams in a String

Problem statement

https://leetcode.com/problems/find-all-anagrams-in-a-string/

Solution

Iterate over string s with windows of length of string p, keep count of symbols, as well as number of frequencies which are correct. We can update all of this in O(1), on each iteration adding one symbol to the end, and removing one symbol from the beginning.

Complexity

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

Code

class Solution:
    def findAnagrams(self, s, p):
        dict_p, dict_s = Counter(p), defaultdict(int)
        num_to_correct, ans = len(dict_p), []
            
        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.append(i - len(p) +1)           
                    
        return ans

Remark

Very similar to problem 0567. Permutation in String.