438. Find All Anagrams in a String

Given strings s and p, return the start indices of every substring of s that is an anagram of p, in any order.

Keep the letter counts of p minus the counts of the current window, and how many letters are still unbalanced. Sliding adds one letter on the right and removes one on the left; when nothing is unbalanced, the window is an anagram.

1function findAnagrams(s: string, p: string): number[] {
2  const need = new Map<string, number>();
3  for (const c of p) need.set(c, (need.get(c) ?? 0) + 1);
4  let off = need.size; const res: number[] = [];
5  const bump = (c: string, d: number) => {
6    const before = need.get(c) ?? 0, after = before + d;
7    need.set(c, after);
8    if (before === 0) off++; else if (after === 0) off--;
9  };
10  for (let r = 0; r < s.length; r++) {
11    bump(s[r], -1);
12    if (r >= p.length) bump(s[r - p.length], +1);
13    if (off === 0) res.push(r - p.length + 1);
14  }
15  return res;
16}

unbalanced = 3

s

need (p count − window count)

result

empty

Count p. 3 distinct letter(s) unbalanced.

1 / 0

Space: play/pause · ←/→: step