438. Find All Anagrams in a String

mediumAsked at Microsoft

Find 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 Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-19

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^4
s and p consist of lowercase English letters.

Examples

Example 1

Input

s = "cbaebabacd", p = "abc"

Output

[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

Input

s = "abab", p = "ab"

Output

[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.

Output

Press Run or Cmd+Enter to execute

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.

Practice these live with InterviewChamp.AI

Drill Find All Anagrams in a String and other Microsoft interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →