Find All Anagrams in a String (Sliding Window)

Problem

Given two strings s and p, return all start indices of p's anagrams in s, using a fixed-size sliding window of frequency counts.

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

Python Solution

def find_anagrams(s, p):
    if len(p) > len(s):
        return []
    need = [0] * 26
    window = [0] * 26
    for ch in p:
        need[ord(ch) - ord('a')] += 1
    result = []
    for i, ch in enumerate(s):
        window[ord(ch) - ord('a')] += 1
        if i >= len(p):
            window[ord(s[i - len(p)]) - ord('a')] -= 1
        if window == need:
            result.append(i - len(p) + 1)
    return result

C++ Solution

vector<int> findAnagrams(string s, string p) {
    if (p.size() > s.size()) return {};
    vector<int> need(26, 0), window(26, 0);
    for (char ch : p) need[ch - 'a']++;
    vector<int> result;
    for (int i = 0; i < s.size(); i++) {
        window[s[i] - 'a']++;
        if (i >= p.size()) window[s[i - p.size()] - 'a']--;
        if (window == need) result.push_back(i - p.size() + 1);
    }
    return result;
}

Java Solution

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

Complexity

Time: O(n · 26) — each position updates a fixed 26-slot array and compares two fixed-size arrays, so effectively O(n). Space: O(1) — two 26-slot frequency arrays, independent of input length.