Find All Anagrams in a String
Problem
s and p of lowercase letters, return every
index i where the substring of s starting at i with
length |p| is an anagram of p (same letters, same counts,
any order). The indices may be returned in any order.s="cbaebabacd", p="abc"Output[0,6]s="abab", p="ab"Output[0,1,2]1 ≤ |s|, |p| ≤ 3·104 · lowercase English letters only
Try it yourself
class Solution {
public List<Integer> findAnagrams(String s, String p) {
}
}
|p|, so use a
fixed-size sliding window: moving one step changes only two letter counts. Track
how many letters of p are still missing to test a window in O(1).Instinct Longest, shortest or count of contiguous subarrays/substrings meeting a rule? Grow a window on the right, shrink it on the left, never step back.
Memory hack Move like a caterpillar - the head stretches forward to grab, the tail pulls up only when the body breaks the rule.
Open the Sliding Window guide →Approaches
Brute ForceSort Every Window
O(n · m log m)Space O(m)Two strings are anagrams iff their sorted forms are equal. Sort
p once, then sort each length-m window of s
(n = |s|, m = |p|) and compare.
public List<Integer> findAnagrams(String s, String p) { List<Integer> res = new ArrayList<>(); char[] target = p.toCharArray(); Arrays.sort(target); for (int i = 0; i + p.length() <= s.length(); i++) { char[] win = s.substring(i, i + p.length()).toCharArray(); Arrays.sort(win); if (Arrays.equals(win, target)) res.add(i); } return res; }
Simple, but re-sorts overlapping windows — slow when m is large.
BetterSliding Window + Two Count Arrays
O(m + 26·n)Space O(1)Keep letter counts of p and of the current window in two
int[26]. Sliding right adds one letter and removes one, then the
two arrays are compared (26 checks).
public List<Integer> findAnagrams(String s, String p) { List<Integer> res = new ArrayList<>(); int n = s.length(), m = p.length(); int[] pCount = new int[26], wCount = new int[26]; for (char c : p.toCharArray()) pCount[c - 'a']++; for (int i = 0; i < n; i++) { wCount[s.charAt(i) - 'a']++; if (i >= m) wCount[s.charAt(i - m) - 'a']--; // drop left char if (i >= m - 1 && Arrays.equals(pCount, wCount)) res.add(i - m + 1); } return res; }
Linear in n, but pays a 26-element comparison at every position.
OptimalSliding Window + Missing Counter
O(n + m)Space O(1)need[c] = count in p minus count in window;
missing = letters of p not yet covered. An incoming
letter with need > 0 covers one (missing--); an outgoing
letter whose need becomes positive uncovers one. A full-length window
with missing == 0 is an anagram.
public List<Integer> findAnagrams(String s, String p) { List<Integer> res = new ArrayList<>(); int n = s.length(), m = p.length(); int[] need = new int[26]; for (char c : p.toCharArray()) need[c - 'a']++; int missing = m; for (int i = 0; i < n; i++) { if (need[s.charAt(i) - 'a']-- > 0) missing--; if (i >= m && ++need[s.charAt(i - m) - 'a'] > 0) missing++; if (missing == 0) res.add(i - m + 1); } return res; }
Dry runs="abab", p="ab"
- i=0ai wbaba needed → missing=1
- i=1awbi wabmissing=0 → add 0
- i=2abwai wb+a(extra) -a → add 1
- i=3abawbi w+b(extra) -b → add 2 ✔
Each step is O(1); no per-window array comparison.
missing starts at m, it cannot hit 0 before
the window is full — no explicit i ≥ m-1 check is needed.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Sort Every Window | O(n · m log m) | O(m) |
| Better | Sliding Window + Two Count Arrays | O(m + 26·n) | O(1) |
| Optimal | Sliding Window + Missing Counter | O(n + m) | O(1) |
- Not handling
|p| > |s|— the brute force loop bound must bei + m ≤ n. - Removing
s[i-m+1]instead ofs[i-m]— window shrinks to m-1. - Using a variable-size window (shrink on mismatch) — anagram windows are always exactly m long.
- Confirm the alphabet: 26 lowercase letters allows
int[26]instead of a map. - Start with the two-array window, then optimise the comparison with a counter.
- Point out that Permutation in String (567) is the same check returning a boolean.