Skip to main content

22. Find All Anagrams in a String

mediumAsked at Figma

Return all start indices where an anagram of pattern p occurs in string s. Figma uses this as a sliding-window probe before pivoting to CRDT operation-window questions.

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. The strings consist of lowercase English letters. You may return the answer 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]

Example 2

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

Approaches

1. Recompute window counts

For each window of size p.length, build the count vector from scratch and compare to p's vector.

Time
O(n * k)
Space
O(1)
function findAnagrams(s, p) {
  const out = [], k = p.length;
  for (let i = 0; i + k <= s.length; i++) {
    if (isAnagram(s.slice(i, i + k), p)) out.push(i);
  }
  return out;
}

Tradeoff:

2. Sliding window with delta tracking

Maintain a 26-length count diff; track a 'matches' counter that increments when a letter's diff reaches zero. O(1) work per window step instead of rebuilding — same shape as how a CRDT replica tracks per-letter ops in a sliding ack window.

Time
O(n)
Space
O(1)
function findAnagrams(s, p) {
  const out = [];
  if (s.length < p.length) return out;
  const need = new Array(26).fill(0);
  const have = new Array(26).fill(0);
  for (const ch of p) need[ch.charCodeAt(0) - 97]++;
  const k = p.length;
  for (let i = 0; i < s.length; i++) {
    have[s.charCodeAt(i) - 97]++;
    if (i >= k) have[s.charCodeAt(i - k) - 97]--;
    if (i >= k - 1 && have.every((v, j) => v === need[j])) out.push(i - k + 1);
  }
  return out;
}

Tradeoff:

Figma-specific tips

Figma values the sliding-window delta pattern as transferable to CRDT operation buffers — connect the dots when you explain it.

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

Practice these live with InterviewChamp.AI →