Skip to main content

31. Find All Anagrams in a String

mediumAsked at Meta

Find every starting index where a pattern's anagram appears in text — Meta's content-search and hashtag-matching pipelines use this sliding-window frequency-map pattern to surface variations without expensive sort-based comparisons.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

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 rearrangement of all characters of a string.

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: s[0..2] = 'cba' is an anagram of 'abc'; s[6..8] = 'bac' is an anagram of 'abc'.

Example 2

Input
s = "abab", p = "ab"
Output
[0,1,2]

Approaches

1. Sort-based (brute force)

Sort p; for each window of length |p| in s, sort the window and compare. Correct but very slow for large inputs.

Time
O(n * k log k)
Space
O(k)
function findAnagrams(s, p) {
  const sorted = p.split('').sort().join('');
  const k = p.length, res = [];
  for (let i = 0; i <= s.length - k; i++) {
    if (s.slice(i, i+k).split('').sort().join('') === sorted) res.push(i);
  }
  return res;
}

Tradeoff:

2. Sliding window frequency map (optimal)

Maintain frequency counts for p and the current window plus a matches counter for characters in sync. Slide one character at a time updating matches incrementally. O(n) total.

Time
O(n)
Space
O(1) — fixed 26-char alphabet
function findAnagrams(s, p) {
  if (p.length > s.length) return [];
  const pCount = new Array(26).fill(0);
  const wCount = new Array(26).fill(0);
  const a = 'a'.charCodeAt(0);
  for (const c of p) pCount[c.charCodeAt(0) - a]++;
  let matches = 0;
  const res = [];
  for (let i = 0; i < s.length; i++) {
    const ri = s.charCodeAt(i) - a;
    wCount[ri]++;
    if (wCount[ri] === pCount[ri]) matches++;
    else if (wCount[ri] === pCount[ri] + 1) matches--;
    if (i >= p.length) {
      const li = s.charCodeAt(i - p.length) - a;
      wCount[li]--;
      if (wCount[li] === pCount[li]) matches++;
      else if (wCount[li] === pCount[li] - 1) matches--;
    }
    if (matches === 26) res.push(i - p.length + 1);
  }
  return res;
}

Tradeoff:

Meta-specific tips

Meta uses this problem to probe the sliding-window pattern and your ability to track state incrementally. The matches-counter trick is the interview differentiator — avoid comparing the entire frequency array on each slide. A common follow-up is 'what if the alphabet is Unicode?' — switch to a Map with a single needs counter instead of a fixed 26-element array.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →