#438 Find All Anagrams in a String
the problem
In plain words
Return every index of s where a rearrangement of p begins — that is, every window of s with exactly the same letter counts as p. The indices may be returned in any order.
in s = "cbaebabacd", p = "abc"
out [0,6]
"cba" starts at 0 and "bac" starts at 6.
in s = "abab", p = "ab"
out [0,1,2]
"ab", "ba", "ab" — matches may overlap.
- 1 ≤ s.length, p.length ≤ 3·10⁴
- Lowercase English letters
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternSliding window (fixed size)Frequency counting
It is Permutation in String that doesn't stop at the first hit: slide a window of size |p|, keep the letter-count difference up to date, and record the start every time all letters balance.
solutions
From brute force to optimal
A window is an anagram of p exactly when its sorted letters equal p's sorted letters.
- Sort p once.
- For each window of size m in s: copy it, sort it, compare.
- Record the start of every equal window.
n − m + 1 windows, each sorted in m log m (m = |p|, n = |s|).
The sorted copy of one window (the answer list aside).
class Solution { public List<Integer> findAnagrams(String s, String p) { List<Integer> starts = new ArrayList<>(); char[] target = p.toCharArray(); Arrays.sort(target); for (int start = 0; start + p.length() <= s.length(); start++) { char[] window = s.substring(start, start + p.length()).toCharArray(); Arrays.sort(window); // m log m per window if (Arrays.equals(window, target)) starts.add(start); } return starts; }}Keep have[26] for the window and compare it with need[26] after every slide.
- need = counts of p.
- For each right: add s[right]; once right ≥ m, remove s[right − m].
- When the window is full and Arrays.equals(need, have), record right − m + 1.
O(1) per slide plus a 26-element comparison.
Two arrays of 26 (the answer list aside).
class Solution { public List<Integer> findAnagrams(String s, String p) { List<Integer> starts = new ArrayList<>(); int m = p.length(); if (m > s.length()) return starts; int[] need = new int[26], have = new int[26]; for (char c : p.toCharArray()) need[c - 'a']++; for (int right = 0; right < s.length(); right++) { have[s.charAt(right) - 'a']++; // one letter in if (right >= m) have[s.charAt(right - m) - 'a']--; // one letter out if (right >= m - 1 && Arrays.equals(need, have)) starts.add(right - m + 1); } return starts; }}diff[c] = need − have and bad = letters whose diff isn't 0. Only the letter entering and the letter leaving can change bad.
- diff = counts of p; bad = number of non-zero entries.
- Letter in: if its diff was 0, bad++; decrement it; if it is now 0, bad−−.
- Letter out (once right ≥ m): the mirror, with an increment.
- If the window is full and bad == 0, record right − m + 1.
Counting p once, then truly O(1) per slide.
One array of 26 and a counter (the answer list aside).
class Solution { public List<Integer> findAnagrams(String s, String p) { List<Integer> starts = new ArrayList<>(); int m = p.length(); if (m > s.length()) return starts; int[] diff = new int[26]; // need minus have, per letter for (char c : p.toCharArray()) diff[c - 'a']++; int bad = 0; // letters whose count is still off for (int d : diff) if (d != 0) bad++; for (int right = 0; right < s.length(); right++) { int in = s.charAt(right) - 'a'; if (diff[in] == 0) bad++; // was balanced, now off by one if (--diff[in] == 0) bad--; if (right >= m) { int out = s.charAt(right - m) - 'a'; if (diff[out] == 0) bad++; if (++diff[out] == 0) bad--; } if (right >= m - 1 && bad == 0) starts.add(right - m + 1); } return starts; }}Dry run
in the room
How to say it in the interview
talk track
- Translate first: "an anagram starts at i" = "the window [i, i + |p| − 1] has p's letter counts".
- Fixed window of size |p|: one letter in, one letter out per step.
Arrays.equalson twoint[26]is already O(26·n) = O(n). Offer thebadcounter as the truly O(1)-per-slide version.
traps
- Returning after the first match — that's LC 567. Here you collect every start.
- Recording before the window is full: only when
right >= m - 1. - Forgetting the early return when p is longer than s.
what they ask next
Follow-ups
What if the strings could hold any Unicode characters?
Swap int[26] for a HashMap<Character, Integer> and keep the same bad counter; only the entering and leaving characters change.
Count the anagram windows instead of listing them?
Same loop with a counter instead of a list — O(n) time, O(1) space.
before you submit
Edge cases to test
- p longer than s → an empty list.
- Overlapping matches: "abab" with "ab" → [0, 1, 2].
- Repeated letters in p: "baa" with "aa" needs two a's → [1].
- s equal to p → [0].
practise next
Similar problems
- #567Permutation in StringMediumin Sliding Window
- #242Valid AnagramEasyin Arrays & Strings
- #49Group AnagramsMediumin Arrays & Strings