Skip to main content

19. Find All Anagrams in a String

mediumAsked at GitHub

Sliding window with character frequency maps to find all anagram start indices — a pattern used in GitHub's fuzzy file-name and diff-string search.

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

Problem

Given strings s and p, return a list of all start indices of p's anagrams in s. An anagram is a permutation of characters, and output can be 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. Brute force: check every window

For each start index, extract a substring of length p, sort both, and compare.

Time
O(n*L*log L)
Space
O(L)
// For each i in 0..s.length-p.length
//   if s.slice(i,i+p.length).split('').sort().join('') === p.split('').sort().join('')
//   result.push(i)

Tradeoff:

2. Fixed-size sliding window with frequency array

Maintain two 26-element frequency arrays (pattern and window). Slide a window of size p.length across s, incrementing/decrementing counts, and record index when arrays match.

Time
O(n)
Space
O(1) — 26-char alphabet
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]++;
  }
  if (pCount.join()===wCount.join()) 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 (pCount.join()===wCount.join()) result.push(i-p.length+1);
  }
  return result;
}

Tradeoff:

GitHub-specific tips

GitHub string-processing questions reward candidates who can articulate the sliding window invariant clearly — practice stating exactly what pCount and wCount represent at each step before writing code.

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

Practice these live with InterviewChamp.AI →