438. Find All Anagrams in a String

At a Glance

Topic: sliding-window
Pattern: Sliding Window
Difficulty: Medium
Companies: Amazon, Google, Meta, Microsoft, Bloomberg
Frequency: High
LeetCode: 438

Problem (one-liner)

Given strings needle and haystack (here pattern and stream), return all start indices of substrings in stream that are anagrams of pattern (same length, same letter counts).

Recognition Cues

Same fixed window + multiset equality as permutation-in-string
Output is list of indices, not boolean
Rolling count + mismatch counter optimization common

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Brute force — sort/compare each window — O(n * m log m).
Better — rolling 26-length vectors — O(n) with each step O(26) compare or track diff.
Optimal — rolling counts + diff counter how many letters still mismatch — O(n) time / O(1) space.

Optimal Solution

Go

func findAnagrams(stream string, pattern string) []int {
	out := []int{}
	if len(pattern) > len(stream) {
		return out
	}
	want := [26]int{}
	for index := range pattern {
		want[pattern[index]-'a']++
	}
	window := [26]int{}
	for index := 0; index < len(pattern); index++ {
		window[stream[index]-'a']++
	}
	if window == want {
		out = append(out, 0)
	}
	for index := len(pattern); index < len(stream); index++ {
		window[stream[index]-'a']++
		window[stream[index-len(pattern)]-'a']--
		if window == want {
			out = append(out, index-len(pattern)+1)
		}
	}
	return out
}

JavaScript

function findAnagrams(stream, pattern) {
	const starts = [];
	if (pattern.length > stream.length) {
		return starts;
	}
	const want = new Array(26).fill(0);
	for (let index = 0; index < pattern.length; index++) {
		want[pattern.charCodeAt(index) - 97]++;
	}
	const window = new Array(26).fill(0);
	for (let index = 0; index < pattern.length; index++) {
		window[stream.charCodeAt(index) - 97]++;
	}
	if (arraysEqual(window, want)) {
		starts.push(0);
	}
	for (let index = pattern.length; index < stream.length; index++) {
		window[stream.charCodeAt(index) - 97]++;
		window[stream.charCodeAt(index - pattern.length) - 97]--;
		if (arraysEqual(window, want)) {
			starts.push(index - pattern.length + 1);
		}
	}
	return starts;
}

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