Skip to main content

21. Find All Anagrams in a String

mediumAsked at Baidu

Return every start index in s where a substring of length |p| is an anagram of p.

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 output may be in any order.

Constraints

  • 1 <= s.length, p.length <= 3 * 10^4
  • Only 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. Sort each window

Slide a window of size |p| across s, sort it, compare to sorted p.

Time
O(n * L log L)
Space
O(L)
const ps=[...p].sort().join('');const out=[];for(let i=0;i+p.length<=s.length;i++)if([...s.slice(i,i+p.length)].sort().join('')===ps)out.push(i);return out;

Tradeoff:

2. Sliding window with char counts

Maintain a count array for the current window and compare to p's count array; slide by adjusting counts as one char enters and one leaves.

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

Tradeoff:

Baidu-specific tips

Baidu uses this exact pattern to spot query-rewriting candidates whose tokens permute, so they expect the O(n) char-count sliding window plus a remark on the 26-entry compare being effectively constant.

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

Practice these live with InterviewChamp.AI →