Given two strings s and p, return an array of all the start indices of p's anagrams in s.
An anagram of p is any rearrangement of all of p's letters that uses each letter exactly as many times as it appears in p. A start index i qualifies when the length-p.length substring of s beginning at i is such an anagram.
Return the indices in ascending order.
Example
The substring "cba" at index 0 and "bac" at index 6 are anagrams of "abc".
Constraints
- 1 <= s.length, p.length <= 3 * 10^4
sandpconsist of lowercase English letters.
Intuition
An anagram of p is just a window of s with the same letter counts as p. The most direct approach slides a length-p.length window across s and, at each position, recomputes the window's counts from scratch and compares them to p's.
function findAnagrams(s, p) {
const result = [];
// Letter counts that p requires.
const need = {};
for (const c of p) need[c] = (need[c] ?? 0) + 1;
// Try every window of width p.length.
for (let i = 0; i + p.length <= s.length; i++) {
// Recount this whole window, then compare to need.
const have = {};
for (let j = i; j < i + p.length; j++) have[s[j]] = (have[s[j]] ?? 0) + 1;
const isAnagram = Object.keys(need).length === Object.keys(have).length &&
Object.keys(need).every((c) => need[c] === have[c]);
if (isAnagram) result.push(i);
}
return result;
}Rebuilding the window's counts every step throws away work — consecutive windows differ by only one letter in and one letter out. Can we do better?
Keep a single have count and update it incrementally: as the window advances, increment the entering letter and decrement the leaving one. That's a fixed-size sliding window of width p.length.
Comparing all 26 counts each step would still cost O(26) per window. So track one number, matches — how many of the 26 letter-counts currently agree with p. Each letter that enters or leaves changes only its own slot, so matches is nudged up or down in O(1). The window is an anagram exactly when matches === 26.
(In the walkthrough `right` is the entering index and `left = right - p.length` is the leaving index — the same two edges the stored solution uses.)
Walking it through:
s = "cbaebabacd", p = "abc" — width-3 window, need {a:1, b:1, c:1}
First full window "cba" — every count agrees with "abc". Record start index 0.
Window "bae" — the stray "e" (and missing "c") break the match. Not an anagram.
Window "bab" has two b's and no c — counts disagree, skip.
Window "bac" matches again — record start index 6.
Last window "acd" — "d" isn't in "abc". Result: [0, 6].
Optimization
Fixed-size sliding window with a match counter
Both s and p are lowercase letters, so each can be summarized by a 26-slot frequency array. A length-p.length window of s is an anagram of p exactly when its 26 counts equal p's counts.
Rather than re-compare all 26 slots each step, track a matches count of how many of the 26 letters currently agree between the window and p. When a letter enters or leaves the window, only that one letter's count changes, so matches is updated in O(1): if a slot transitions into agreement bump matches, if it transitions out of agreement drop it. The window is an anagram whenever matches === 26.
O(s.length) time, O(1) space (a fixed 26-letter alphabet).
function findAnagrams(s, p) {
const result = [];
if (p.length > s.length) return result;
const A = 'a'.charCodeAt(0);
// need[c]: target count of letter c from p; have[c]: count in the current window.
const need = new Array(26).fill(0);
const have = new Array(26).fill(0);
for (const ch of p) need[ch.charCodeAt(0) - A]++;
// matches: how many of the 26 letter-counts currently agree with p.
let matches = 0;
for (let i = 0; i < 26; i++) {
if (need[i] === have[i]) matches++;
}
for (let right = 0; right < s.length; right++) {
// Add the entering letter, adjusting matches for just that slot.
const enter = s.charCodeAt(right) - A;
have[enter]++;
if (have[enter] === need[enter]) matches++; // moved into agreement
else if (have[enter] === need[enter] + 1) matches--; // moved out of agreement
// Once the window is too wide, drop the leftmost letter.
const left = right - p.length;
if (left >= 0) {
const exit = s.charCodeAt(left) - A;
have[exit]--;
if (have[exit] === need[exit]) matches++; // moved into agreement
else if (have[exit] === need[exit] - 1) matches--; // moved out of agreement
}
// All 26 counts agree → this window is an anagram of p.
if (matches === 26) result.push(right - p.length + 1);
}
return result;
}Complexity analysis
Time complexity: O(n). Here's why:
- Building
p's counts is O(p.length), and the one-time comparison of the 26 slots is O(1). - The window then slides across
sonce; each step adds one letter and removes one, updatingmatchesin O(1) rather than re-scanning all 26 counts.
So the scan is O(n) where n = s.length (the p pre-pass is dominated by it).
Space complexity: O(1). Here's why:
needandhaveare fixed 26-slot arrays regardless of input size.- The
matchescounter is a single integer.
The extra space is O(1) for a fixed alphabet. The output array isn't counted; it can hold up to O(n) indices in the worst case.
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| s = "xy", p = "xyz" | [] | Pattern longer than the text — early return, no windows. |
| s = "az", p = "za" | [0] | Single window, reordered letters — an anagram at index 0. |
| s = "abcabc", p = "abc" | [0,1,2,3] | A periodic string — every length-3 window is an anagram. |
| s = "hello", p = "ll" | [2] | Repeated letters in the pattern — only the "ll" window matches counts. |
| s = "pqrs", p = "tu" | [] | Pattern letters never appear — no match anywhere. |
| s = "abcba", p = "abc" | [0,2] | Two anagrams ("abc" and "cba") around a non-matching middle window. |
Try it yourself
Write your solution against the real judge before checking the reference.