438. Find All Anagrams in a String

At a Glance

• Topic: Hash Table
• Pattern: Analyze Pattern
• Difficulty: Medium
• LeetCode: 438

Problem Statement

Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.

Example 1:

Input: s = "cbaebabacd", p = "abc" Output: [0,6] Explanation: The substring with start index = 0 is "cba", which is an anagram of "abc". The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input: s = "abab", p = "ab" Output: [0,1,2] Explanation: The substring with start index = 0 is "ab", which is an anagram of "ab". The substring with start index = 1 is "ba", which is an anagram of "ab". The substring with start index = 2 is "ab", which is an anagram of "ab".

Constraints:

1 <= s.length, p.length <= 3 * 104
s and p consist of lowercase English letters.

Approach & Solution Steps

• 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 JS Solution

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;
}

Edge Cases & Pitfalls

• Always consider empty or null inputs.
• Watch out for off-by-one index errors.