Domain 2MediumCORE

Find All Anagrams in a String

We are given two strings: s (the text to search in) and p (the pattern whose anagrams we seek). We need to identify every starting index in s such that the substring of length equal to len(p) beginning at that index is an anagram of p.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Hash Table

438. Find All Anagrams in a String

Model: qwen3.5:9b
Topics: Hash Table
FAANG asked: 1
Acceptance rate: 45.2%


Problem Breakdown

We are given two strings: s (the text to search in) and p (the pattern whose anagrams we seek). We need to identify every starting index in s such that the substring of length equal to len(p) beginning at that index is an anagram of p.

Key Inputs:

  • String s: The source string.
  • String p: The target pattern for anagrams.

Outputs: A list of integers representing start indices in s where the substring starting there matches the character frequency count of p. Order does not matter.

Constraints & Edge Cases:

  1. Length Constraint: Both strings are up to ~20,000 characters (NN). This suggests we need a linear time complexity solution O(N)O(N) rather than quadratic or worse.
  2. Character Set: Lowercase English letters only (‘a’-‘z’). This allows us to use fixed-size arrays (size 26) instead of hash maps for frequency counting, which is more performant in Python due to hashing overhead and lower memory footprint.
  3. Empty/Short Strings: If len(s) < len(p), no anagrams are possible; return empty list immediately.

Intuition

A brute-force approach would be to iterate through every substring of length p within s. For each position, we extract the substring and check if it is an anagram of p (e.g., by sorting both or counting characters).

Why Brute Force Fails: Sorting takes O(Mlog⁡M)O(M \log M) where MM is the window size. Doing this for every starting index in a string of length NN results in roughly O(N⋅Mlog⁡M)O(N \cdot M \log M). Given constraints, we need something faster than that.

Key Insight: Anagrams are defined by character frequency counts. If two strings have identical frequencies for all characters ‘a’ through ‘z’, they are anagrams. Instead of recalculating the entire count map from scratch at every step (which is O(M)O(M)), we can use a Sliding Window. As we move one position to the right in s, only two things change:

  1. We add a new character entering our window on the right.
  2. We remove an old character leaving the window on the left (if it exists).

We maintain a frequency map for the pattern p and update a running frequency map for the current window in s. Since the alphabet size is fixed at 26, comparing these maps takes constant time O(1)O(1). This reduces our overall complexity to linear.

Approach

  1. Initialize: Create two arrays of size 26: one representing character counts for string p (target_counts) and another for the current window in s (window_counts).
    • Populate target_counts based on string p. Initialize the window in s for indices [0, len(p)-1], updating window_counts.
  2. Pre-process: Check if anagram exists at index 0 immediately after initialization (before sliding). If so, add to results list.
  3. Slide Window: Iterate through s starting from index len(p):
    • Add character at current index (i) to the window count (add).
    • Remove character that slides out of the window (at index i - len(p)), decrementing its count (remove).
  4. Check Match: After updating counts, compare window_counts with target_counts. If they are identical, append current start index to results list. The loop logic handles checking at every step after the window is fully formed (size = len(p)).

Complexity Analysis

  • Time Complexity: O(N)O(N) where NN is length of string s. We iterate through s once. Inside the iteration, we perform constant-time operations: updating character counts and comparing two arrays of fixed size 26 (O(1)O(1) relative to input). Thus, it scales linearly with input size.
  • Space Complexity: O(1)O(1) auxiliary space (excluding output). The frequency maps are limited to alphabet size (26), which is a constant regardless of string length N.

Solution

from typing import List

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        # Edge case: if pattern is longer than text, no anagram possible
        if len(p) > len(s):
            return []
        
        n = len(s)
        m = len(p)
        
        # Use fixed-size arrays for frequency counting (faster than dict/Counter in tight loops)
        target_counts = [0] * 26
        window_counts = [0] * 26
        
        base_ord = ord('a')

        # Populate target counts for p
        for char in p:
            target_counts[ord(char) - base_ord] += 1
            
        results = []

        # Initialize first window (indices 0 to m-1)
        for i, char in enumerate(s):
            if i < m:
                window_counts[ord(char) - base_ord] += 1
        
        # Check match at index 0 immediately after initialization
        if target_counts == window_counts:
            results.append(0)

        # Slide the window from s[m] to end of string
        for i in range(m, n):
            new_char_idx = ord(s[i]) - base_ord       # Character entering window
            old_char_idx = ord(s[i - m]) - base_ord   # Character leaving window
            
            window_counts[new_char_idx] += 1    # Add incoming char
            window_counts[old_char_idx] -= 1    # Remove outgoing char
            
            if target_counts == window_counts:
                results.append(i - m + 1)

        return results

Edge Cases Handled

  • len(s) < len(p): The code checks this immediately and returns an empty list.
  • No Anagrams Found: If target_counts != window_counts at any step, the index is not added; function correctly returns whatever matches were found (possibly empty).
  • Overlapping Windows: The sliding logic handles overlaps naturally by incrementing/decrementing counts for adjacent indices without re-scanning.
  • Empty Pattern/Text: While constraints say p is non-empty, if s was empty and passed the length check implicitly via loop ranges (handled), it would return an empty list as expected.