Find All Anagrams in a String

Examples

Input: s = "cbaebabacd", p = "abc"
Output: [0, 6]

The substring starting at index 0 is "cba" (an anagram of "abc"), and the one starting at index 6 is "bac" (also an anagram).

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

Substrings "ab" (index 0), "ba" (index 1), and "ab" (index 2) are all anagrams of "ab".

Input: s = "af", p = "be"
Output: []

No substring of s of length 2 uses the same letters as "be".

Constraints

• 1 <= s.length, p.length <= 3 * 10^4

• s and p consist of lowercase English letters.

Approach

This is essentially "Permutation in String," but instead of stopping at the first match, every matching starting index needs to be collected.

Build the letter counts for p once, and the counts for the first window of s (of the same length as p). Slide that window across s one character at a time: each slide adds the new character on the right and removes the one falling off the left, so the counts update in constant time rather than being recomputed. After every slide (including the very first window), compare the window's counts to p's counts — whenever they match exactly, the window's starting index is an anagram match, so record it.

Solutions

Brute Force — Recount Every Window

For every window of s the same length as p, build its letter counts from scratch and compare them to p's counts, collecting every start index that matches.

function findAnagrams(s, p) {
  const result = [];
  const need = buildCounts(p);
  const windowSize = p.length;

  for (let start = 0; start + windowSize <= s.length; start++) {
    const have = buildCounts(s.slice(start, start + windowSize));
    if (sameCounts(need, have)) {
      result.push(start);
    }
  }

  return result;
}

function buildCounts(str) {
  const counts = {};
  for (const ch of str) {
    counts[ch] = (counts[ch] || 0) + 1;
  }
  return counts;
}

function sameCounts(a, b) {
  const keys = new Set([...Object.keys(a), ...Object.keys(b)]);
  for (const key of keys) {
    if ((a[key] || 0) !== (b[key] || 0)) return false;
  }
  return true;
}

Time: O(n * m) — n windows, each costing O(m) to build and compare, m = p.length · Space: O(26) per window comparison

Optimal — Fixed-Size Sliding Window

Maintain one running count array for the current window, updated by adding and removing a single letter as the window slides, and check it against p's counts after each slide.

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

  const need = new Array(26).fill(0);
  const have = new Array(26).fill(0);
  const base = "a".charCodeAt(0);

  for (let i = 0; i < p.length; i++) {
    need[p.charCodeAt(i) - base]++;
    have[s.charCodeAt(i) - base]++;
  }

  if (matches(need, have)) result.push(0);

  for (let right = p.length; right < s.length; right++) {
    have[s.charCodeAt(right) - base]++;
    const left = right - p.length;
    have[s.charCodeAt(left) - base]--;

    if (matches(need, have)) {
      result.push(left + 1);
    }
  }

  return result;
}

function matches(a, b) {
  for (let i = 0; i < 26; i++) {
    if (a[i] !== b[i]) return false;
  }
  return true;
}

Time: O(n + m) — n = s.length, m = p.length, comparisons are a constant 26 slots · Space: O(26) — constant, two fixed-size count arrays