Find All Anagrams in a String

You are given two strings, s and p, of lowercase English letters. A substring of s is an anagram of p if it uses exactly the same letters as p, each the same number of times, in any order.

Return the starting indices (0-based) of every substring of s that is an anagram of p, in increasing order. Substrings may overlap. If there are none, return an empty list.

Example 1

Example 2

Example 3

Constraints

• 1 <= s.length, p.length <= 3 · 104
• s and p contain only lowercase English letters

Pattern Path · Sliding Window · problem 53 of 169

Start simple

For each start index, sort or count the substring of length m and compare it with p: O(n·m) time.

The key idea

Since an anagram has the same length as p, the candidates are the windows s[i..i+m-1] with m = len(p). Two strings are anagrams exactly when they have identical letter counts, so the question becomes: for which windows does the letter count equal that of p?

Recounting every window costs O(m) each. A sliding window avoids that: moving from window i-1 to window i adds one letter on the right and removes one on the left, so only two counters change. Keep the counts for p and for the current window in two arrays of size 26 (or two dictionaries) and compare them after each step.

Comparing two 26-element arrays is constant time, so the scan is O(26·n) = O(n). You can even drop that factor by tracking how many of the 26 letters currently have matching counts and updating it when a counter changes, but the plain comparison is already linear and easier to get right.

Remember to handle m > len(s): there are no windows, and the answer is empty.

Complexity

• Time: O(n)
• Space: O(1) (26 counters)

Python

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        m = len(p)
        if m > len(s):
            return []

        def index(ch):
            return ord(ch) - ord("a")

        need = [0] * 26
        window = [0] * 26
        for ch in p:
            need[index(ch)] += 1

        result = []
        for i, ch in enumerate(s):
            window[index(ch)] += 1          # letter entering on the right
            if i >= m:
                window[index(s[i - m])] -= 1  # letter leaving on the left
            if i >= m - 1 and window == need:
                result.append(i - m + 1)
        return result

JavaScript

var findAnagrams = function(s, p) {
  const m = p.length;
  if (m > s.length) return [];
  const index = (ch) => ch.charCodeAt(0) - 97;

  const need = new Array(26).fill(0);
  const window = new Array(26).fill(0);
  for (const ch of p) need[index(ch)]++;

  const sameCounts = () => need.every((count, k) => count === window[k]);
  const result = [];
  for (let i = 0; i < s.length; i++) {
    window[index(s[i])]++;               // letter entering on the right
    if (i >= m) window[index(s[i - m])]--; // letter leaving on the left
    if (i >= m - 1 && sameCounts()) result.push(i - m + 1);
  }
  return result;
};

What the interviewer is checking

This tests whether you recognise a fixed-size sliding window and update state incrementally rather than recomputing it for every position.

Mistakes to avoid

• Off-by-one errors when deciding which character leaves the window (it is s[i - m] when s[i] enters).
• Checking the first full window too late or skipping the last one.
• Forgetting the case where p is longer than s.

Follow-ups to expect

• Can you avoid comparing 26 counters each step? (Track number of matching letters.)
• What if the alphabet were all of Unicode? (Hash maps; drop zero-count keys.)
• Only need to know if any anagram exists? (Return at first match.)

In real software

Fixed-size rolling statistics like this power network intrusion signatures, DNA k-mer composition scans and rate counters over the last N events.

Practice next