Find All Anagrams in a String

1. Define the problem

Given strings s and p, return every start index where a fixed-size window of s is an anagram of p . Slide a window of length p, updating letter counts, and record every index whose counts match p. Order of indices does not matter.

Constraints

1 ≤ s.length, p.length ≤ 3 × 10⁴
s and p consist of lowercase English letters

Example

Inputs = "cbaebabacd", p = "abc"

Output[0, 6]

Explanation Substrings "cba" at 0 and "bac" at 6 are anagrams of "abc".

2. Know the words first

In plain terms

Anagram: A word or phrase made by rearranging all the letters of another, using each one exactly once — like 'listen' and 'silent'.

3. Visualize the solution

Record every window matching p's counts

Statusmatch

Window "cba" matches need — record index 0.

What happens in this step

window = [0, 2]  ("cba")   need = {a:1, b:1, c:1}

built from s[0..2]:
  window = {c:1, b:1, a:1}

window counts exactly match need — record start index 0.

Step 1 of 5

Steps to visualize

Build need counts from p and a fixed window of length p over s.
If the window counts match need, record the start index.
Slide one step: increment the entering char, decrement the leaving char.
Record every later start index whose counts match again.
Stop when the window reaches the end of s.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Record every window matching p's counts

Statusmatch

Window "cba" matches need — record index 0.

What happens in this step

window = [0, 2]  ("cba")   need = {a:1, b:1, c:1}

built from s[0..2]:
  window = {c:1, b:1, a:1}

window counts exactly match need — record start index 0.

Step 1 of 5

5. Solution

Solution

solution.tsTypeScript

function findAnagrams(s, p) {
  const result = [];
  const n = p.length;
  const m = s.length;
  if (n > m) return result;

  const need = new Array(26).fill(0);
  const window = new Array(26).fill(0);
  const a = 'a'.charCodeAt(0);

  for (let i = 0; i < n; i++) {
    need[p.charCodeAt(i) - a]++;
    window[s.charCodeAt(i) - a]++;
  }

  const matches = () => {
    for (let i = 0; i < 26; i++) {
      if (need[i] !== window[i]) return false;
    }
    return true;
  };

  if (matches()) result.push(0);

  for (let right = n; right < m; right++) {
    window[s.charCodeAt(right) - a]++;
    const left = right - n;
    window[s.charCodeAt(left) - a]--;
    if (matches()) result.push(left + 1);
  }

  return result;
}

Time: O(n)
Space: O(1) + O(n) output

6. Test cases

Test cases

Input	Expected	Covers
`s = "cbaebabacd", p = "abc"`	`[0, 6]`	Docstring example
`s = "a", p = "a"`	`[0]`	Single character match
`s = "bca", p = "abc"`	`[0]`	Entire s is an anagram of p
`s = "xyz", p = "abc"`	`[]`	No valid window
`s = "aaaa", p = "aa"`	`[0, 1, 2]`	All identical characters
`s = "ab", p = "abc"`	`[]`	p longer than s
`s = "abababab", p = "aab"`	`[0, 2, 4]`	Every other index matches {a:2,b:1}

Find All Anagrams in a String