Skip to main content

23. Find All Anagrams in a String

mediumAsked at Dropbox

Find every start index where a permutation of a pattern appears in a string — Dropbox applies the sliding-window frequency technique when scanning file content for duplicate chunks during deduplication.

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

Problem

Given two strings s and p, return an array of all start indices of p's anagrams in s. An anagram is any permutation of p. The answer can be returned in any order.

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' and s[6..8] = 'bac' are both anagrams of 'abc'.

Example 2

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

Approaches

1. Sliding window with frequency sort

Slide a window of length p.length across s; sort each window's characters and compare to sorted p. Simple but slow due to repeated sorting.

Time
O(n * k log k) where k = p.length
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. Sliding window with character count

Maintain two frequency arrays of size 26 — one for p and one for the current window. Slide the window, updating counts incrementally. Compare arrays in O(26) = O(1).

Time
O(n)
Space
O(1) — fixed 26-char arrays
function findAnagrams(s, p) {
  const result = [];
  if (s.length < p.length) return result;
  const pCount = new Array(26).fill(0);
  const wCount = new Array(26).fill(0);
  const a = 'a'.charCodeAt(0);
  for (let i = 0; i < p.length; i++) {
    pCount[p.charCodeAt(i) - a]++;
    wCount[s.charCodeAt(i) - a]++;
  }
  const equals = () => pCount.every((v, i) => v === wCount[i]);
  if (equals()) result.push(0);
  for (let i = p.length; i < s.length; i++) {
    wCount[s.charCodeAt(i) - a]++;
    wCount[s.charCodeAt(i - p.length) - a]--;
    if (equals()) result.push(i - p.length + 1);
  }
  return result;
}

Tradeoff:

Dropbox-specific tips

Dropbox may re-frame this as: 'Given two files, find all byte-ranges in file B that are permutations of a given chunk from file A.' The key insight Dropbox cares about is recognizing that the sliding window achieves O(1) per step by maintaining a diff counter instead of comparing full arrays — mention the 'matches' counter optimization if you have time.

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

Practice these live with InterviewChamp.AI →