LeetCode · #438

Find All Anagrams in a String Solution

Given strings s and p, return an array of all start indices of p's anagrams in s.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #438

🏗️

Pattern

Sliding Window — fixed size + frequency

Given two strings s and p, return an array of all the start indices of p's anagrams in s. An anagram is a rearrangement — same characters, same counts, different order. You may return the answer in any order.

Example

 Input: s = "cbaebabacd",  p = "abc" Output: [0, 6]
// "cba" at index 0 and "bac" at index 6 are anagrams of "abc" 

Constraints

 • 1 ≤ s.length, p.length ≤ 3 × 10⁴ • s and p consist of lowercase English letters 

Section Two · Approach 1

Brute Force — Sort Each Window

For every window of size len(p) in s, sort the window and compare with sorted p. Record indices where they match.

Problem: Sorting each window costs O(k log k). A sliding frequency array updates in O(1) per slide — just add the entering character and remove the leaving one.

Java — Sort Each Window

 import java.util.*;
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> result = new ArrayList<>();
char[] target = p.toCharArray();
Arrays.sort(target);
for (int i = 0; i <= s.length() - p.length(); i++) {
char[] window = s.substring(i, i + p.length()).toCharArray();
Arrays.sort(window);
if (Arrays.equals(target, window)) result.add(i);
        }
return result;
    }
}

Python — Sort Each Window

 class Solution:
def findAnagrams(self, s: str, p: str) -> list[int]:
        target = sorted(p)
        k = len(p)
return [i for i in range(len(s) - k + 1) if sorted(s[i:i+k]) == target]

Metric	Value
Time	O(n · k log k)
Space	O(k)

Section Three · Approach 2

Fixed-Size Sliding Window — O(n)

This problem is nearly identical to LC 567 (Permutation in String) — the difference is we collect all matching indices instead of returning at the first match. Same algorithm: fixed window of size len(p), frequency comparison via a matches counter.

💡 Mental model: Same cookie-cutter analogy as LC 567. Slide a window of size len(p) across s. At each position, incrementally update the frequency counts. When all 26 character counts match between the window and p, record the starting index.

Algorithm

Step 1: Build pCount[26] and initial sCount[26] from first len(p) chars.
Step 2: Initialize matches = number of equal slots (0–26).
Step 3: If matches == 26, add index 0 to result.
Step 4: Slide window: add right char, remove left char, update matches.
Step 5: If matches == 26 after a slide, add left + 1 to result.

🎯 LC 438 vs LC 567:

These are the same problem — 567 asks "does any anagram exist?" (return bool), 438 asks "where are all anagrams?" (return list of indices).
The sliding window logic is identical; only the output collection differs.

Section Four · Trace

Visual Walkthrough

Trace through s = "cbaebabacd", p = "abc":

Fixed Window of size 3 — slide and check frequency match

Section Five · Implementation

Code — Java & Python

Java — Sliding Window with matches counter

 import java.util.*;
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> result = new ArrayList<>();
if (p.length() > s.length()) return result;
int[] pCount = new int[26], sCount = new int[26];
for (int i = 0; i < p.length(); i++) {
            pCount[p.charAt(i) - 'a']++;
            sCount[s.charAt(i) - 'a']++;
        }
int matches = 0;
for (int i = 0; i < 26; i++)
if (pCount[i] == sCount[i]) matches++;
if (matches == 26) result.add(0);
for (int r = p.length(); r < s.length(); r++) {
int addIdx = s.charAt(r) - 'a';
            sCount[addIdx]++;
if (sCount[addIdx] == pCount[addIdx]) matches++;
else if (sCount[addIdx] == pCount[addIdx] + 1) matches--;
int remIdx = s.charAt(r - p.length()) - 'a';
            sCount[remIdx]--;
if (sCount[remIdx] == pCount[remIdx]) matches++;
else if (sCount[remIdx] == pCount[remIdx] - 1) matches--;
if (matches == 26) result.add(r - p.length() + 1);
        }
return result;
    }
}

Python — Sliding Window with matches counter

 class Solution:
def findAnagrams(self, s: str, p: str) -> list[int]:
if len(p) > len(s): return []

        p_count = [0] * 26
s_count = [0] * 26 for i in range(len(p)):
            p_count[ord(p[i]) - ord('a')] += 1
s_count[ord(s[i]) - ord('a')] += 1
matches = sum(1 for i in range(26) if p_count[i] == s_count[i])
        result = [0] if matches == 26 else []
for r in range(len(p), len(s)):
            idx = ord(s[r]) - ord('a')
            s_count[idx] += 1 if s_count[idx] == p_count[idx]: matches += 1 elif s_count[idx] == p_count[idx] + 1: matches -= 1
idx = ord(s[r - len(p)]) - ord('a')
            s_count[idx] -= 1 if s_count[idx] == p_count[idx]: matches += 1 elif s_count[idx] == p_count[idx] - 1: matches -= 1 if matches == 26: result.append(r - len(p) + 1)
return result

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Sort each window	O(n · k log k)	O(k)	Rebuilds sort per slide
Matches counter ← optimal	O(n)	O(1)	O(1) per slide; 26-slot arrays

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
p longer than s	`s="ab", p="abc"`	Empty result — no window possible.
Entire string is anagram	`s="abc", p="cab"`	Single result: [0].
Overlapping anagrams	`s="abab", p="ab"`	[0, 1, 2] — windows overlap. All valid.
All same chars	`s="aaaa", p="aa"`	[0, 1, 2] — every window of size 2 matches.
No match	`s="xyz", p="ab"`	Empty result.

⚠ Common Mistake: Off-by-one in the start index when recording results. After sliding the window right by adding s[r] and removing s[r - len(p)], the new window starts at r - len(p) + 1. Getting this index wrong shifts all results by 1.

← Back to Sliding Window problems

LearningTree

LC 438 · Find All Anagrams in a String — Solution & Explanation | DSA Guide