Find All Anagrams in a String

medium string hash map sliding window

Problem

Given strings s and p, return all start indices of substrings in s that are anagrams of p.

Inputs = "cbaebabacd", p = "abc"

Output[0, 6]

"cba" and "bac" are anagrams of "abc".

def find_anagrams(s, p):
    if len(s) < len(p): return []
    need = [0] * 26
    have = [0] * 26
    for ch in p: need[ord(ch) - 97] += 1
    res = []
    for i, ch in enumerate(s):
        have[ord(ch) - 97] += 1
        if i >= len(p):
            have[ord(s[i - len(p)]) - 97] -= 1
        if have == need:
            res.append(i - len(p) + 1)
    return res

function findAnagrams(s, p) {
  if (s.length < p.length) return [];
  const need = new Array(26).fill(0);
  const have = new Array(26).fill(0);
  for (const ch of p) need[ch.charCodeAt(0) - 97]++;
  const res = [];
  const eq = (a, b) => a.every((v, i) => v === b[i]);
  for (let i = 0; i < s.length; i++) {
    have[s.charCodeAt(i) - 97]++;
    if (i >= p.length) have[s.charCodeAt(i - p.length) - 97]--;
    if (eq(have, need)) res.push(i - p.length + 1);
  }
  return res;
}

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

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

Explanation

An anagram of p is just any arrangement of the same letters, so two strings are anagrams exactly when their letter counts match. We slide a window the size of p across s and check the counts at each position.

We build a fixed 26-slot array need from p, and a second array have for the current window. As we move right, we add the new letter s[i], and once the window is full (i >= len(p)) we remove the letter that just left on the left side, s[i - len(p)].

Whenever have == need, the current window is an anagram, and we record its start index i - len(p) + 1. Comparing two 26-length arrays is constant work, so each window check is cheap.

Example: s = "cbaebabacd", p = "abc". The window "cba" at index 0 matches the counts of "abc", and later "bac" starting at index 6 matches too, giving [0, 6].

Because each character is added once and removed once, the scan is linear in the length of s plus p.

Time: O(|s| + |p|) Space: O(1)