438. Find All Anagrams in a String

Quick Identifier

• Topic: sliding-window
• Pattern: Sliding Window (Fixed Window + Frequency Match)
• Hint: Find anagrams of p inside s. Anagrams have the exact same character frequencies. Use a fixed-size window of length p.length and compare frequency maps.
• Difficulty: Medium
• Companies: Amazon, Google, Meta, Microsoft, Bloomberg
• LeetCode: 438

Quick Sights

• Time Complexity: O(n). We initialize the first window in $O(p)$ time, then slide it across s taking $O(1)$ per step. Comparing the two size-26 arrays at each step is an $O(26) = O(1)$ operation.
• Space Complexity: O(1). We only need two integer arrays of fixed size 26 (one for p's frequencies, one for the current window's frequencies).
• Core Mechanism: Since an anagram must be exactly the same length as p, our sliding window's size never changes after initialization. For every step rightward, we add the new character to our window's frequency array, and subtract the character that just fell out the left side. If the window's frequency array matches p's frequency array, we record the left index.

Concept Explanation

As a senior engineer, the leap here is understanding that an "anagram" is just a multiset equality problem. The exact sequence of characters doesn't matter; only their counts do.

1. The Target Signature: First, scan the target string p. Build a "signature" of it—a simple size-26 array counting how many times each letter appears.
2. The Fixed Frame: Because any valid anagram must be exactly p.length characters long, we don't need a complex variable window that expands and shrinks unpredictably. We just build a rigid frame of length p.length.
3. The Rolling Hash (Frequency): Place this frame over the start of string s. Count the letters inside. Does it match the Target Signature? If yes, record the start index.
4. The Slide: Now, grab the frame and shift it exactly one spot to the right.
   • One old letter falls out of the left side (decrement its count).
   • One new letter enters the right side (increment its count).
   • Check if the signatures match again.
   • Repeat until the frame hits the end of s. This single-step slide ensures we never recalculate the whole frame from scratch.

Diagram

This flowchart illustrates the fixed sliding window mechanics and the $O(1)$ rolling update.

Study Pattern (SDE3+)

• 0–3 min: Clarify that $O(n \cdot m \log m)$ sorting per window is naive. Mention that maintaining a running frequency array drops it to $O(n \cdot 26) = O(n)$.
• Implementation pass: Use Go [26]int equality or a JS helper function to compare the two arrays. Ensure you initialize the very first window before entering the main slide loop.
• 5 min extension: How would you optimize the array comparison if the alphabet was all 1M+ Unicode characters? You couldn't compare arrays of size 1M efficiently. You would track a single integer mismatches (the number of distinct characters whose counts differ). When mismatches == 0, you have an anagram.

Approaches

• Brute force — For every index, extract substring of length $m$, sort it, compare to sorted $p$. Time: $O(n \cdot m \log m)$.
• Acceptable — Sliding window with Hash Map. Time: $O(n)$ but Hash Map equality is heavier.
• Optimal — Sliding window with size-26 integer arrays. Go allows direct array comparison if a == b. JS requires a small loop. Time: $O(n)$. (Pick this)

Optimal Solution

Go

func findAnagrams(s string, p string) []int {
	out := []int{}
	if len(p) > len(s) {
		return out
	}
	
	want := [26]int{}
	for i := 0; i < len(p); i++ {
		want[p[i]-'a']++
	}
	
	window := [26]int{}
	// Initialize the first window
	for i := 0; i < len(p); i++ {
		window[s[i]-'a']++
	}
	
	// Check the first window
	if window == want {
		out = append(out, 0)
	}
	
	// Slide the window
	for right := len(p); right < len(s); right++ {
		// Add the new character on the right
		window[s[right]-'a']++
		// Remove the old character from the left
		window[s[right-len(p)]-'a']--
		
		if window == want {
			out = append(out, right-len(p)+1)
		}
	}
	
	return out
}

JavaScript

function findAnagrams(s, p) {
	const out = [];
	if (p.length > s.length) return out;
	
	const want = new Array(26).fill(0);
	const window = new Array(26).fill(0);
	
	// Initialize frequencies for the target and the first window
	for (let i = 0; i < p.length; i++) {
		want[p.charCodeAt(i) - 97]++;
		window[s.charCodeAt(i) - 97]++;
	}
	
	if (arraysEqual(window, want)) {
		out.push(0);
	}
	
	// Slide the window
	for (let right = p.length; right < s.length; right++) {
		// Add the new character
		window[s.charCodeAt(right) - 97]++;
		// Remove the character that left the window
		window[s.charCodeAt(right - p.length) - 97]--;
		
		if (arraysEqual(window, want)) {
			// The start index of the current window is right - p.length + 1
			out.push(right - p.length + 1);
		}
	}
	
	return out;
}

function arraysEqual(a, b) {
	for (let i = 0; i < 26; i++) {
		if (a[i] !== b[i]) return false;
	}
	return true;
}

Walkthrough

Input: s = "cbaebabacd", p = "abc" (Lengths: s = 10, p = 3) want = [a:1, b:1, c:1]

Output: [0, 6]

Edge Cases

• p is longer than s (Immediately return empty array).
• Multiple overlapping anagrams (e.g., s = "aaaa", p = "aa". Should return [0, 1, 2]).

Pitfalls

• Forgetting to check the very first window before entering the sliding loop.
• Off-by-one errors calculating the left index. The character dropping out is at index right - p.length. The start index of the newly formed valid window is right - p.length + 1.

Similar Problems

• 567. Permutation in String — Exact same logic, but returns a single boolean instead of an array of indices.
• 076. Minimum Window Substring — Variable window where the target is a subset, not an exact length match.

Mind-Map Tags

#sliding-window #fixed-window #anagram #all-indices #frequency-match