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:
- Length Constraint: Both strings are up to ~20,000 characters (). This suggests we need a linear time complexity solution rather than quadratic or worse.
- 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.
- 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 where is the window size. Doing this for every starting index in a string of length results in roughly . 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 ), we can use a Sliding Window. As we move one position to the right in s, only two things change:
- We add a new character entering our window on the right.
- 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 . This reduces our overall complexity to linear.
Approach
- Initialize: Create two arrays of size 26: one representing character counts for string
p(target_counts) and another for the current window ins(window_counts).- Populate
target_countsbased on stringp. Initialize the window insfor indices[0, len(p)-1], updatingwindow_counts.
- Populate
- Pre-process: Check if anagram exists at index 0 immediately after initialization (before sliding). If so, add to results list.
- Slide Window: Iterate through
sstarting from indexlen(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).
- Add character at current index (
- Check Match: After updating counts, compare
window_countswithtarget_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: where is length of string
s. We iterate throughsonce. Inside the iteration, we perform constant-time operations: updating character counts and comparing two arrays of fixed size 26 ( relative to input). Thus, it scales linearly with input size. - Space Complexity: 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_countsat 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
pis non-empty, ifswas empty and passed the length check implicitly via loop ranges (handled), it would return an empty list as expected.