Anagram Problems — Sorting Key, Frequency Vector, and Rolling Hash

Anagram Core Patterns

1. Group Anagrams — Sort Key

from collections import defaultdict

def groupAnagrams(strs):
    groups = defaultdict(list)
    for s in strs:
        key = tuple(sorted(s))
        groups[key].append(s)
    return list(groups.values())

2. Group Anagrams — Frequency Vector (faster)

def groupAnagrams(strs):
    groups = defaultdict(list)
    for s in strs:
        key = [0]*26
        for c in s: key[ord(c)-ord('a')] += 1
        groups[tuple(key)].append(s)
    return list(groups.values())

3. Find All Anagrams in a String — Sliding Window

from collections import Counter

def findAnagrams(s, p):
    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
        c = s[i-len(p)]
        window[c] -= 1
        if window[c] == 0: del window[c]
        if window == need: res.append(i-len(p)+1)
    return res

JavaScript

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

Java

import java.util.*;
public List<Integer> findAnagrams(String s,String p){
    int[]need=new int[26],win=new int[26]; for(char c:p.toCharArray())need[c-'a']++;
    int m=p.length(); for(int i=0;i<m&&i<s.length();i++)win[s.charAt(i)-'a']++;
    List<Integer>res=new ArrayList<>(); if(Arrays.equals(need,win))res.add(0);
    for(int i=m;i<s.length();i++){win[s.charAt(i)-'a']++;win[s.charAt(i-m)-'a']--;if(Arrays.equals(need,win))res.add(i-m+1);}
    return res;
}

C++

#include <vector>
#include <string>
using namespace std;
vector<int> findAnagrams(string s,string p){
    vector<int>need(26,0),win(26,0); for(char c:p)need[c-'a']++;
    int m=p.size(); for(int i=0;i<m&&i<(int)s.size();i++)win[s[i]-'a']++;
    vector<int>res; if(need==win)res.push_back(0);
    for(int i=m;i<(int)s.size();i++){win[s[i]-'a']++;win[s[i-m]-'a']--;if(need==win)res.push_back(i-m+1);}
    return res;
}

C

/* C: int[26] frequency arrays, memcmp to compare */