Find All Anagrams in a String

Medium · Sliding Window · Explanation and code example

Sliding Window (Optimal)

How it works

Comparing two arrays of 26 elements after every slide takes extra time. We can optimize by tracking how many of the 26 character counts currently match between the window and the pattern. When we add or remove a character, we only update the match count for that specific character. If all 26 counts match, we found an anagram.

Steps

  1. Build frequency arrays pCount and sCount for the initial window.
  2. Count how many of the 26 characters have matching frequencies (initialize match).
  3. If match == 26, add index 0 to the result.
  4. Slide the window across s:
    • For the character leaving the window: update its count and adjust match accordingly.
    • For the character entering the window: update its count and adjust match accordingly.
    • If match == 26, add the current left index to the result.
  5. Return the result list.

Complexity

  • Time complexity: O(n + m)
  • Space complexity: O(1) since we have at most 26 different characters.

Where n is the length of the string s and m is the length of the string p.

Things to watch for

Forgetting Edge Case When Pattern is Longer Than String

If the pattern p is longer than the string s, there cannot be any anagrams. Failing to handle this edge case at the start can lead to index out of bounds errors or incorrect empty results being returned for the wrong reason.

Incorrect Window Size Management

When sliding the window, it is easy to make off-by-one errors with the window boundaries. The window must always be exactly len(p) characters wide. Adding a character before removing one, or vice versa, can temporarily create windows of incorrect size and lead to false matches.

Inefficient Frequency Comparison

Comparing two frequency arrays or maps after every window slide takes O(26) or O(k) time where k is the alphabet size. While this is technically constant, it adds overhead. The optimal approach tracks how many character counts currently match between the window and pattern, updating this count incrementally as characters enter and leave the window.

Python code example

from typing import List

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

        pCount = [0] * 26
        sCount = [0] * 26
        for i in range(m):
            pCount[ord(p[i]) - ord('a')] += 1
            sCount[ord(s[i]) - ord('a')] += 1

        match = sum(1 for i in range(26) if pCount[i] == sCount[i])
        res = []
        if match == 26:
            res.append(0)

        l = 0
        for r in range(m, n):
            c = ord(s[l]) - ord('a')
            if sCount[c] == pCount[c]:
                match -= 1
            sCount[c] -= 1
            l += 1
            if sCount[c] == pCount[c]:
                match += 1

            c = ord(s[r]) - ord('a')
            if sCount[c] == pCount[c]:
                match -= 1
            sCount[c] += 1
            if sCount[c] == pCount[c]:
                match += 1

            if match == 26:
                res.append(l)

        return res

C++ code example

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int n = s.size(), m = p.size();
        if (m > n) return {};

        vector<int> pCount(26, 0), sCount(26, 0);
        for (int i = 0; i < m; i++) {
            pCount[p[i] - 'a']++;
            sCount[s[i] - 'a']++;
        }

        int match = 0;
        for (int i = 0; i < 26; i++) {
            if (pCount[i] == sCount[i]) match++;
        }

        vector<int> res;
        if (match == 26) res.push_back(0);

        int l = 0;
        for (int r = m; r < n; r++) {
            int c = s[l] - 'a';
            if (sCount[c] == pCount[c]) match--;
            sCount[c]--;
            l++;
            if (sCount[c] == pCount[c]) match++;

            c = s[r] - 'a';
            if (sCount[c] == pCount[c]) match--;
            sCount[c]++;
            if (sCount[c] == pCount[c]) match++;

            if (match == 26) res.push_back(l);
        }

        return res;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode Watch NeetCode on YouTube

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations