LeetCode 438: Find All Anagrams in a String

An anagram of p is a window in s, so we can use sliding window.

Variable-length window

We expand the window until we get at least the required count for each character in p. Then we shrink to get the window size right. If the shrunk window still has all characters by the required count, we have found an anagram.

To efficiently detect when the window has the right count for each character, we maintain two pieces of information:

p_map: Count per distinct p-char.
- p_map[c] > 0: We have p_map[c] instances of the char c still missing.
- p_map[c] = 0: We have just the right count for the char c.
- p_map[c] < 0: We have abs(p_map[c]) instances of the char c in excess.
match_count: Count of distinct p-char’s we have found by at least the required count. It is running summary of p_map.
- Increases by one when p_map[c] becomes 0.
- Decreases by one when p_map[c] becomes positive.

Say len(s) = $n$ and len(p) = $m$ .

Time: $\mathcal{O}(n)$ , space: $\mathcal{O}(m)$ .

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        p_map = {}
        for c in p:
            p_map[c] = p_map.get(c, 0) + 1
        
        match_count = 0
        begin = 0
        anagrams = []
        for end, c in enumerate(s):
            if c not in p_map:
                continue
            
            # Expand window
            p_map[c] -= 1
            if p_map[c] == 0:
                match_count += 1
            if match_count < len(p_map):
                continue
            
            # Shrink window
            while end-begin+1 > len(p):
                d = s[begin]
                begin += 1
                if d not in p_map:
                    continue
                if p_map[d] == 0:
                    match_count -= 1
                p_map[d] += 1
            
            if match_count == len(p_map):
                anagrams.append(begin)
    
        return anagrams

Fixed-length window

For each start index we can look at a window of size len(p).

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        window = {}
        for c in p:
            window[c] = window.get(c, 0) + 1
        
        match_count = 0
        begin = 0
        anagrams = []
        for end, c in enumerate(s):
            if c in window:
                window[c] -= 1
                if window[c] == 0:
                    match_count += 1
            
            if end-begin+1 < len(p):
                continue

            if match_count == len(window):
                anagrams.append(begin)
            
            del_char = s[begin]
            begin += 1

            if del_char in window:
                if window[del_char] == 0:
                    match_count -= 1
                window[del_char] += 1
    
        return anagrams

unreasonably effective