438. Find All Anagrams in a String
mediumAsked at MicrosoftFind All Anagrams in a String is Microsoft's clean sliding-window-with-frequency-matching question. Maintain a window of length p over s; compare frequencies on each slide. The clever variant — track only a diff counter instead of comparing maps — is the optimization Microsoft hopes you reach.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Microsoft loops.
- Glassdoor (2026-Q1)— Microsoft Bing/Office org onsite reports list this as a recurring 30-minute sliding-window medium.
- Blind (2025-12)— Microsoft L60 reports include Find All Anagrams with the 'optimize past array equality' follow-up.
Problem
Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order. An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Constraints
1 <= s.length, p.length <= 3 * 10^4s and p consist of lowercase English letters.
Examples
Example 1
s = "cbaebabacd", p = "abc"[0,6]Explanation: The substring starting at index 0 is 'cba', which is an anagram of 'abc'. The substring starting at index 6 is 'bac', which is an anagram of 'abc'.
Example 2
s = "abab", p = "ab"[0,1,2]Approaches
1. Sliding window with two frequency arrays
Build a 26-array freq for p. Slide a window of size |p| across s, maintaining its own 26-array. After each slide, compare the arrays.
- Time
- O(n * 26) = O(n)
- Space
- O(1)
function findAnagrams(s, p) {
const result = [];
if (s.length < p.length) return result;
const need = new Array(26).fill(0);
const have = new Array(26).fill(0);
const A = 'a'.charCodeAt(0);
for (const ch of p) need[ch.charCodeAt(0) - A]++;
for (let i = 0; i < s.length; i++) {
have[s.charCodeAt(i) - A]++;
if (i >= p.length) have[s.charCodeAt(i - p.length) - A]--;
if (i >= p.length - 1 && need.every((v, k) => v === have[k])) {
result.push(i - p.length + 1);
}
}
return result;
}Tradeoff: Linear in n with a constant 26-cell comparison. Easy to write; the .every() is O(26) per step which is fine for the constraints.
2. Sliding window with diff counter (optimal)
Track a single integer 'matches' counting how many of the 26 chars currently have have[c] === need[c]. Increment/decrement matches on each window slide.
- Time
- O(n)
- Space
- O(1)
function findAnagrams(s, p) {
const result = [];
if (s.length < p.length) return result;
const need = new Array(26).fill(0);
const have = new Array(26).fill(0);
const A = 'a'.charCodeAt(0);
for (const ch of p) need[ch.charCodeAt(0) - A]++;
let needNonZero = 0;
for (const v of need) if (v > 0) needNonZero++;
let matched = 0;
for (let i = 0; i < s.length; i++) {
const inIdx = s.charCodeAt(i) - A;
have[inIdx]++;
if (have[inIdx] === need[inIdx]) matched++;
else if (have[inIdx] === need[inIdx] + 1) matched--;
if (i >= p.length) {
const outIdx = s.charCodeAt(i - p.length) - A;
have[outIdx]--;
if (have[outIdx] === need[outIdx]) matched++;
else if (have[outIdx] === need[outIdx] - 1) matched--;
}
if (matched === needNonZero) result.push(i - p.length + 1);
}
return result;
}Tradeoff: True O(n) — no per-slide comparison loop. The matched counter is the entire optimization. Microsoft will accept the first version but the diff counter is the answer they're hoping to see in a hot loop.
Microsoft-specific tips
Microsoft cares about the sliding-window invariant. State: 'I maintain a window of length |p| over s. Each slide is one in, one out — O(1) update — so the total work across all slides is O(n).' The matched-counter optimization is the bonus; the array-comparison version still passes. Lead with whichever you can write cleanly under time pressure.
Common mistakes
- Reinitializing have[] inside the loop — turns O(n) into O(n * |p|).
- Comparing strings via .slice() and .sort() inside the loop — that's O(n * |p| log |p|) and times out on the upper-bound constraints.
- Off-by-one on when to start collecting answers (must wait until i >= p.length - 1).
Follow-up questions
An interviewer at Microsoft may pivot to one of these next:
- Permutation in String (LC 567) — same window, return true/false instead of all indices.
- Minimum Window Substring (LC 76) — variable-size window with target frequency.
- Group Anagrams (LC 49) — categorize, no window.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Is the .every() comparison really O(1)?
It's O(26) which is bounded constant. Fine for the constraints, but if |p| were large, the matched-counter version saves the 26-factor.
Does the alphabet matter?
Constraints say lowercase only — 26 entries. For Unicode you'd switch to a Map and the same logic applies, but the array indexing is faster.
Free learning resources
Curated free links for this problem.