LeetCode Solutions Blog

Find All Anagrams in a String

Number: 438

Difficulty: Medium

Paid? No

Problem Description

Given two strings s and p, return an array of all start indices of p's anagrams in s. An anagram of p is any permutation of the characters in p. The order of the returned indices does not matter.

Key Insights

Use a sliding window of length equal to p over s.
Maintain frequency counts of characters in p and within the current window in s.
Compare frequency counts to determine if the current window is an anagram.
Update the window efficiently by adding one character and removing the character that goes out of the window.

Space and Time Complexity

Time Complexity: O(n) where n is the length of s. Space Complexity: O(1) since we use fixed-size frequency arrays or hash maps.

Solution

We use the sliding window technique to iterate over s with a window size equal to the length of p. First, count the frequencies of characters in p. Then, iterate over s and update a frequency count for the current window. When the window size equals the length of p, compare the two frequency counts. If they match, record the start index. To slide the window efficiently, increment the count for the incoming character and decrement the count for the outgoing character. This way, we achieve an O(n) solution that is optimal for the problem constraints.

Code Solutions

# Define the function to find all anagram indices in the string
def findAnagrams(s: str, p: str):
    # Import Counter for frequency counting
    from collections import Counter
    # List to store the starting indices of all anagrams
    result = []
    # Length of string p
    p_length = len(p)
    # Frequency count for characters in p
    p_count = Counter(p)
    # Frequency count for the current window in s
    s_count = Counter()
    
    # Iterate over the string s
    for i in range(len(s)):
        # Add current character to the window count
        s_count[s[i]] += 1
        
        # Remove the leftmost character from window if window size exceeds p_length
        if i >= p_length:
            if s_count[s[i - p_length]] == 1:
                del s_count[s[i - p_length]]  # Remove key completely if count becomes 0
            else:
                s_count[s[i - p_length]] -= 1
        
        # Compare window count with p_count when window size is equal to p_length
        if s_count == p_count:
            result.append(i - p_length + 1)
    
    return result

# Example usage:
print(findAnagrams("cbaebabacd", "abc"))  # Expected output: [0, 6]