Skip to main content

31. Find All Anagrams in a String

mediumAsked at Box

Return every starting index where a permutation of a pattern appears in a text — Box uses a sliding-window approach identical to this when scanning large file contents for permutations of security-sensitive keyword patterns during compliance checks.

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 (permutations) in s. You may return the answer in any order. An anagram is a rearrangement of all characters in 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: Index 0: "cba" is an anagram of "abc". Index 6: "bac" is an anagram of "abc".

Example 2

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

Approaches

1. Brute force — sort every window

For every window of length p.length in s, sort the window and compare with sorted p. O(n * k log k) where k = p.length.

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

Tradeoff:

2. Optimal — sliding window with frequency count

Maintain two frequency arrays of size 26 — one for p, one for the current window. Slide the window one character at a time: add the incoming char, remove the outgoing char, and compare arrays in O(26) = O(1).

Time
O(n)
Space
O(1) — fixed 26-char alphabet
function findAnagrams(s, p) {
  if (p.length > s.length) return [];
  const result = [];
  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]++;
  const k = p.length;
  for (let i = 0; i < s.length; i++) {
    wCount[s.charCodeAt(i) - a]++;
    if (i >= k) wCount[s.charCodeAt(i - k) - a]--;
    if (i >= k - 1 && pCount.join(',') === wCount.join(',')) {
      result.push(i - k + 1);
    }
  }
  return result;
}

Tradeoff:

Box-specific tips

Box compliance scanning operates on documents that can be gigabytes in size, so they will challenge you on why the O(n) sliding window is not optional — a brute-force O(n * k log k) approach would be too slow for real-time scanning. A sharper optimization: instead of joining and comparing 26-element arrays each step, maintain a 'matches' counter that tracks how many of the 26 character frequencies agree between the window and p, updating it incrementally from O(26) to O(1) per step.

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 Box interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →