Find All Anagrams in a String

Problem

Given two lowercase strings s and p, return every starting index in s whose substring of length p.length is an anagram of p.

Constraints

• 1 ≤ s.length, p.length ≤ 3·10⁴

Approach — Sliding Window

This is a Sliding Window problem. The idea: keep a moving window over the sequence, expanding and shrinking it while tracking the answer in a single pass. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time.

Solution code

Python

class Solution:
    def findAnagrams(self, s, p):
        from collections import Counter
        if len(p) > len(s):
            return []
        need = Counter(p)
        window = Counter(s[:len(p)])
        res = [0] if window == need else []
        for i in range(len(p), len(s)):
            window[s[i]] += 1
            window[s[i-len(p)]] -= 1
            if window[s[i-len(p)]] == 0:
                del window[s[i-len(p)]]
            if window == need:
                res.append(i - len(p) + 1)
        return res

Java

import java.util.*;

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> out = new ArrayList<>();
        if (s.length() < p.length()) return out;
        int[] need = new int[26], have = new int[26];
        for (char c : p.toCharArray()) need[c - 'a']++;
        int k = p.length();
        for (int i = 0; i < s.length(); i++) {
            have[s.charAt(i) - 'a']++;
            if (i >= k) have[s.charAt(i - k) - 'a']--;
            if (Arrays.equals(need, have)) out.add(i - k + 1);
        }
        return out;
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.