Find All Anagrams

Medium

Python

def find_anagrams(s,p):
    from collections import Counter
    need=Counter(p); window=Counter()
    res=[]; l=0
    for r,c in enumerate(s):
        window[c]+=1
        if r>=len(p)-1:
            if window==need: res.append(l)
            window[s[l]]-=1
            if window[s[l]]==0: del window[s[l]]
            l+=1
    return res

Java

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

Key Insight

Python Counter comparison elegant. Java int[26] efficient. c-'a' maps chars to indices.

Python → Java Differences

Counter comparison vs Arrays.equals()
int[26] vs Python Counter
c-'a' index trick for lowercase

Python

def find_anagrams(s,p):
    from collections import Counter
    need=Counter(p); window=Counter()
    res=[]; l=0
    for r,c in enumerate(s):
        window[c]+=1
        if r>=len(p)-1:
            if window==need: res.append(l)
            window[s[l]]-=1
            if window[s[l]]==0: del window[s[l]]
            l+=1
    return res

Java

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

Algorithm Steps

1. Fixed window of p.length
2. Compare at each position

← Previous All Sliding Window Next →