3
k
Return the start indices of every substring of s that is an anagram of p. Slide a fixed-size window of width p.length across s, keep a 26-letter frequency in lockstep, and record the left index every time the window's letters match p — all in O(n).
Find every starting index i in s where the substring s[i .. i + p.length - 1] is an anagram of p (same letters, same counts, any order). s="cbaebabacd", p="abc" → [0, 6] because "cba" starts at index 0 and "bac" starts at index 6. s="abab", p="ab" → [0, 1, 2].
|p| window of s is an anagram of p iff their letter-frequency arrays are identical. Rather than recompute the full count on every slide, keep one integer matches (0–26) tracking how many of the 26 letter-counts currently agree. Each step changes only the entering character (and, once the window is full, the leaving one), so matches shifts by at most ±1 per update. When matches === 26, every count agrees — record the window's left index.p.length > s.length, no window fits — return [].p into a 26-slot array, and seed matches with the unused letters that already agree at 0.s[r]. For each right index, increment have[c]. If the slot just became equal to need, matches++; if it just left equality (overshot), matches--.s[r-k]. Once r ≥ k, the window is too wide — remove the leftmost character and apply the symmetric ±1 update to matches.k (r ≥ k − 1) and matches === 26, push the left index r − k + 1.have[c] goes from equal to over, you must matches--(the slot just stopped agreeing). People who only increment on the "just became equal" path and forget the symmetric decrement get phantom matches and report wrong indices. Both directions must be handled on the add AND the evict.Space is O(1): two number[26]arrays regardless of input size. For arbitrary Unicode you'd swap to a Map and track the number of satisfied keys, giving O(k) space where k = distinct characters in p.
k = 3. Build need[] from p, start have[] empty and matches = 23 (all the unused letters already agree at 0).1function findAnagrams(s: string, p: string): number[] {2 const res: number[] = [];3▶ const k = p.length;4 if (k > s.length) return res;56 // Frequency arrays for p (need) and the current window of s (have)7▶ const need = new Array<number>(26).fill(0);8▶ const have = new Array<number>(26).fill(0);9 const a = 'a'.charCodeAt(0);1011▶ for (const c of p) need[c.charCodeAt(0) - a]++;1213 // matches = number of letters whose count in 'have' equals 'need'14▶ let matches = 0;1516 for (let r = 0; r < s.length; r++) {17 // Add s[r] to the window18 const rIdx = s.charCodeAt(r) - a;19 have[rIdx]++;20 if (have[rIdx] === need[rIdx]) matches++;21 else if (have[rIdx] - 1 === need[rIdx]) matches--;2223 // Once the window exceeds size k, evict the leftmost char24 if (r >= k) {25 const lIdx = s.charCodeAt(r - k) - a;26 have[lIdx]--;27 if (have[lIdx] === need[lIdx]) matches++;28 else if (have[lIdx] + 1 === need[lIdx]) matches--;29 }3031 // Window is exactly size k once r >= k - 132 if (r >= k - 1 && matches === 26) res.push(r - k + 1);33 }34 return res;35}
function findAnagrams(s: string, p: string): number[] {
const res: number[] = [];
const k = p.length;
if (k > s.length) return res;
// Frequency arrays for p (need) and the current window of s (have)
const need = new Array<number>(26).fill(0);
const have = new Array<number>(26).fill(0);
const a = 'a'.charCodeAt(0);
for (const c of p) need[c.charCodeAt(0) - a]++;
// matches = number of letters whose count in 'have' equals 'need'
let matches = 0;
for (let r = 0; r < s.length; r++) {
// Add s[r] to the window
const rIdx = s.charCodeAt(r) - a;
have[rIdx]++;
if (have[rIdx] === need[rIdx]) matches++;
else if (have[rIdx] - 1 === need[rIdx]) matches--;
// Once the window exceeds size k, evict the leftmost char
if (r >= k) {
const lIdx = s.charCodeAt(r - k) - a;
have[lIdx]--;
if (have[lIdx] === need[lIdx]) matches++;
else if (have[lIdx] + 1 === need[lIdx]) matches--;
}
// Window is exactly size k once r >= k - 1
if (r >= k - 1 && matches === 26) res.push(r - k + 1);
}
return res;
}res. If p is longer than s, no window can hold it — return res (empty) immediately.need[] tallies p's letter counts; have[] tracks the sliding window. Both are fixed 26-slot arrays, so space stays O(1).have[c] for the incoming character. If the slot just became equal to need, matches++; if it just overshot equality, matches--. Both directions matter.r >= k the window is one character too wide, so remove s[r-k] and apply the same ±1 logic. This keeps the window exactly k wide from here on.r >= k - 1. If all 26 counts agree (matches === 26), the window is an anagram of p, so push its start index r - k + 1.s, res holds every anagram start index.s enters and leaves the window exactly once, and every update is O(1). O(1) space — two fixed-length arrays of 26 integers regardless of input size (O(k) if you use a map for a larger alphabet).true at the first matching window; here we keep going and collect every left index.number[26] arrays with a Map<string, number> and track the number of satisfied keys instead of the literal constant 26.s and compare to sorted p— O(n · k log k). The count approach reuses the previous window's state, so it never re-sorts: O(n).have differs from need and record when it hits 0. It is the same idea expressed with the complementary count.p, then shrink from the left to minimize length — the window width is no longer fixed.function findAnagrams(s: string, p: string): number[] {
const res: number[] = [];
const k = p.length;
if (k > s.length) return res;
// Frequency arrays for p (need) and the current window of s (have)
const need = new Array<number>(26).fill(0);
const have = new Array<number>(26).fill(0);
const a = 'a'.charCodeAt(0);
for (const c of p) need[c.charCodeAt(0) - a]++;
// matches = number of letters whose count in 'have' equals 'need'
let matches = 0;
for (let r = 0; r < s.length; r++) {
// Add s[r] to the window
const rIdx = s.charCodeAt(r) - a;
have[rIdx]++;
if (have[rIdx] === need[rIdx]) matches++;
else if (have[rIdx] - 1 === need[rIdx]) matches--;
// Once the window exceeds size k, evict the leftmost char
if (r >= k) {
const lIdx = s.charCodeAt(r - k) - a;
have[lIdx]--;
if (have[lIdx] === need[lIdx]) matches++;
else if (have[lIdx] + 1 === need[lIdx]) matches--;
}
// Window is exactly size k once r >= k - 1
if (r >= k - 1 && matches === 26) res.push(r - k + 1);
}
return res;
}s enters and leaves the window exactly once, and every update is O(1). O(1) space — two fixed-length arrays of 26 integers regardless of input size (O(k) if you use a map for a larger alphabet).A window is an anagram of p exactly when its sorted characters equal sorted p. Slide a fixed-width window of length k = p.length across s, sort each window, and compare.
function findAnagrams(s: string, p: string): number[] {
const res: number[] = [];
const k = p.length;
if (k > s.length) return res;
const target = p.split('').sort().join('');
for (let i = 0; i + k <= s.length; i++) {
const window = s.slice(i, i + k).split('').sort().join('');
if (window === target) res.push(i);
}
return res;
}n − k + 1windows costs O(k log k), so the whole scan is O(n · k log k) — every slide throws away the previous window's work. Maintaining a 26-slot frequency count incrementally (one char enters, one leaves per slide) drops it to O(n).Keep the incremental have[] array, but instead of a clever matches counter just compare the two 26-slot arrays on every full window. Simpler to reason about, same asymptotic cost.
function findAnagrams(s: string, p: string): number[] {
const res: number[] = [];
const k = p.length;
if (k > s.length) return res;
const a = 'a'.charCodeAt(0);
const need = new Array<number>(26).fill(0);
const have = new Array<number>(26).fill(0);
for (const c of p) need[c.charCodeAt(0) - a]++;
const equal = (): boolean => {
for (let i = 0; i < 26; i++) if (need[i] !== have[i]) return false;
return true;
};
for (let r = 0; r < s.length; r++) {
have[s.charCodeAt(r) - a]++;
if (r >= k) have[s.charCodeAt(r - k) - a]--;
if (r >= k - 1 && equal()) res.push(r - k + 1);
}
return res;
}matches counter just folds that constant into O(1) per step, which interviewers usually like to see.| "find all start indices of anagrams / permutations of p" | fixed-size sliding window + 26-count match counter; push left index on full match |
| window width is fixed at p.length | add s[r], evict s[r-k] once r >= k — no expand/shrink two-pointer needed |
| comparing letter frequencies of two strings | number[26] need/have arrays + matches counter avoids full recount each slide |
| "return true at first match" instead of all (LC 567) | same window; return true instead of pushing the index |
const res: number[] = [];
const k = p.length;
const need = new Array<number>(26).fill(0);
const have = new Array<number>(26).fill(0);
const a = 'a'.charCodeAt(0);
for (const c of p) need[c.charCodeAt(0) - a]++;
let matches = 0;
for (let r = 0; r < s.length; r++) {
// add s[r] to have; update matches
if (r >= k) { /* remove s[r-k] from have; update matches */ }
if (r >= k - 1 && matches === 26) res.push(r - k + 1);
}
return res;have[c] === need[c] for all 26 letters, i.e. matches === 26.findAnagrams("cbaebabacd", "abc") return?have[c] when adding the right character, when should you decrement matches?findAnagrams("abab", "ab") return?