Leetcode 438. Find All Anagrams in a String

Let's understand what we're being asked to do. We have a string s = "cbaebabacd" and a pattern t = "abc", and we need to find all starting positions in s where an anagram of t appears.

An anagram means the same characters with the same frequencies, but in any order. So "abc", "bca", "cab" are all anagrams of t.

Tracing through s: at index 0, we have "cba" (an anagram of "abc"! add 0 to result). At index 6, we have "bac" (another anagram! add 6 to result). Final answer: [0, 6].

Important constraint: Both strings contain only lowercase English letters. The pattern t has length up to 30,000, and s can be up to 30,000 characters.

Edge cases to consider: What if t is longer than s? (return empty list). What if t has duplicate characters like "aab"? What if s is empty?

The straightforward approach is to check every possible substring of length |t| in string s. For each starting position, extract the substring and verify if it's an anagram by sorting both strings and comparing, or by counting character frequencies from scratch. If they match, add the starting index to the result. This approach is simple but inefficient because we recount characters for overlapping windows.

def find_anagrams(s, t):
    """
    Find all start indices of t's anagrams in s using brute force.
    For each possible substring of length |t|, check if it's an anagram.
    """
    result = []
    p_len = len(t)
    s_len = len(s)
    
    # Edge case: if t is longer than s, no anagrams possible
    if p_len > s_len:
        return result
    
    # Sort t once for comparison
    sorted_p = sorted(t)
    
    # Check every possible starting position
    for i in range(s_len - p_len + 1):
        # Extract substring of length p_len starting at i
        substring = s[i:i + p_len]
        
        # Sort the substring and compare with sorted t
        # This is inefficient because we sort for every window
        if sorted(substring) == sorted_p:
            result.append(i)
    
    return result

Instead of checking every possible substring by sorting or counting characters from scratch, notice that as we move through s, we're only adding one new character and removing one old character from our window.

If we maintain a running count of characters in our current window, we can update it in constant time as we slide forward!

By maintaining character frequencies as we slide through s, we avoid recounting the entire window each time.

This transforms the problem from checking O(n) windows, each taking O(m) time to verify (total O(n*m)), into checking O(n) windows with O(1) updates (total O(n))!

Imagine you have a physical counter for each letter a-z. You set up the counters to match pattern t.

Now slide a window of size |t| through string s. At each position: add the new character entering the window (increment its counter), remove the old character leaving the window (decrement its counter). After each update, check if all counters match the pattern's counters.

The key insight: you're not recounting from scratch - you're making one addition and one subtraction per slide!

The optimal approach uses a sliding window with character frequency counting. First, count the frequency of each character in pattern t. Then slide a window of size |t| through string s, maintaining a frequency count of characters in the current window. As the window slides, add the new character entering and remove the old character leaving in constant time. After each slide, compare the window's frequency map with the pattern's frequency map - if they match, record the starting index. This eliminates redundant recounting of overlapping characters.

def find_anagrams(s, t):
    """
    Find all start indices of anagrams of t in s using sliding window.
    """
    result = []
    
    # Edge case: if t is longer than s, no anagrams possible
    if len(t) > len(s):
        return result
    
    # Build frequency map for pattern t
    p_freq = {}
    for char in t:
        p_freq[char] = p_freq.get(char, 0) + 1
    
    # Initialize sliding window frequency map
    window_freq = {}
    window_size = len(t)
    
    # Build initial window of size len(t)
    for i in range(window_size):
        char = s[i]
        window_freq[char] = window_freq.get(char, 0) + 1
    
    # Check if initial window is an anagram
    if window_freq == p_freq:
        result.append(0)
    
    # Slide the window through string s
    for i in range(window_size, len(s)):
        # Add new character entering the window
        new_char = s[i]
        window_freq[new_char] = window_freq.get(new_char, 0) + 1
        
        # Remove old character leaving the window
        old_char = s[i - window_size]
        window_freq[old_char] -= 1
        if window_freq[old_char] == 0:
            del window_freq[old_char]
        
        # Check if current window is an anagram
        if window_freq == p_freq:
            result.append(i - window_size + 1)
    
    return result

• Sliding window with frequency map: When comparing character multisets (anagrams, permutations) in substrings, use a fixed-size sliding window with hash map frequency counts - this transforms an O(n×m) naive approach into O(n) by reusing computations as the window slides.
• Window validity via counter variable: Instead of comparing two hash maps on every iteration (26 operations), maintain a matches counter tracking how many character frequencies currently match - increment/decrement it as characters enter/leave the window, checking `matches == 26` in O(1).
• Add-then-remove window pattern: When sliding the window, always add the new character first, then remove the old character - this ensures the window size stays correct and prevents off-by-one errors when updating your frequency counts and match tracking.
• Array vs HashMap for fixed alphabet: With only lowercase letters (26 characters), use a fixed-size array[26] instead of a HashMap - it's faster (no hashing overhead), uses less memory, and simplifies iteration when counting matches.
• Anagram detection generalization: This sliding window + frequency counting pattern extends to any fixed-length substring matching problem with character constraints: permutation in string, substring with concatenation of words, or finding all substrings with exactly k distinct characters.
• Real-world plagiarism detection: This technique powers fuzzy string matching in plagiarism checkers and DNA sequence analysis - detecting when text segments contain the same content in different orders, or finding gene subsequences that are permutations of target patterns.