Space

Open

Interview

From Fieldwork

Scales

438. Find All Anagrams in a String

leetcodestringhash-tablesliding-windowmedium

Open pinned source

v1

Fixed-Size Arrays: Since the problem usually constrains input to lowercase English letters, using a list of size 26 ([0] * 26) is significantly faster than using a dictionary (collections.Counter).
Sliding Window Strategy:
We expand the window to the right by incrementing the count of s[i].
Once i reaches the length of p, we start shrinking the window from the left by decrementing the count of s[i - len(p)].
Efficient Comparison: In Python, comparing two lists (p_count == s_count) checks element-by-element equality. Since the lists are always size 26, this comparison is considered O(1).

v1 code

class Solution:
    def findAnagrams(self, s: str, p: str) -> list[int]:
        if len(p) > len(s):
            return []

        p_count = [0] * 26
        s_count = [0] * 26
        result = []
        
        # Calculate frequency for p and the initial window of s
        for char in p:
            p_count[ord(char) - ord('a')] += 1
            
        # Sliding window
        for i in range(len(s)):
            # Add the new character to the current window
            s_count[ord(s[i]) - ord('a')] += 1
            
            # If window size is greater than len(p), remove the leftmost character
            if i >= len(p):
                s_count[ord(s[i - len(p)]) - ord('a')] -= 1
            
            # Compare the frequency arrays
            if p_count == s_count:
                result.append(i - len(p) + 1)
                
        return result

Practice bench

Work the material

Drafts stay on this device.

What is still unclear, or what would change the explanation?

Saved on this device · one draft per mode