438. Find All Anagrams in a String

Problem Description

Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input: s = "abab", p = "ab"
Output: [0,1,2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

Constraints:

• 1 <= s.length, p.length <= 3 * 10⁴
• s and p consist of lowercase English letters.

Python Solution

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        if len(p) > len(s):
            return []
        
        # Initialize frequency counters
        p_count = Counter(p)
        window_count = Counter()
        result = []
        
        # Process first window
        for i in range(len(p)):
            window_count[s[i]] += 1
        
        # Check first window
        if window_count == p_count:
            result.append(0)
        
        # Slide window and check remaining positions
        for i in range(len(p), len(s)):
            # Add new character
            window_count[s[i]] += 1
            # Remove old character
            window_count[s[i - len(p)]] -= 1
            
            # Remove count if zero
            if window_count[s[i - len(p)]] == 0:
                del window_count[s[i - len(p)]]
            
            # Check if current window is anagram
            if window_count == p_count:
                result.append(i - len(p) + 1)
        
        return result

Java Solution

class Solution {
    public List findAnagrams(String s, String p) {
        if (p.length() > s.length()) {
            return new ArrayList<>();
        }
        
        // Initialize frequency arrays
        int[] pCount = new int[26];
        int[] windowCount = new int[26];
        List result = new ArrayList<>();
        
        // Count frequencies in p
        for (char c : p.toCharArray()) {
            pCount[c - 'a']++;
        }
        
        // Process first window
        for (int i = 0; i < p.length(); i++) {
            windowCount[s.charAt(i) - 'a']++;
        }
        
        // Check first window
        if (Arrays.equals(windowCount, pCount)) {
            result.add(0);
        }
        
        // Slide window and check remaining positions
        for (int i = p.length(); i < s.length(); i++) {
            // Add new character
            windowCount[s.charAt(i) - 'a']++;
            // Remove old character
            windowCount[s.charAt(i - p.length()) - 'a']--;
            
            // Check if current window is anagram
            if (Arrays.equals(windowCount, pCount)) {
                result.add(i - p.length() + 1);
            }
        }
        
        return result;
    }
}

C++ Solution

class Solution {
public:
    vector findAnagrams(string s, string p) {
        if (p.length() > s.length()) {
            return {};
        }
        
        // Initialize frequency arrays
        vector pCount(26, 0);
        vector windowCount(26, 0);
        vector result;
        
        // Count frequencies in p
        for (char c : p) {
            pCount[c - 'a']++;
        }
        
        // Process first window
        for (int i = 0; i < p.length(); i++) {
            windowCount[s[i] - 'a']++;
        }
        
        // Check first window
        if (windowCount == pCount) {
            result.push_back(0);
        }
        
        // Slide window and check remaining positions
        for (int i = p.length(); i < s.length(); i++) {
            // Add new character
            windowCount[s[i] - 'a']++;
            // Remove old character
            windowCount[s[i - p.length()] - 'a']--;
            
            // Check if current window is anagram
            if (windowCount == pCount) {
                result.push_back(i - p.length() + 1);
            }
        }
        
        return result;
    }
};

JavaScript Solution

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function(s, p) {
    if (p.length > s.length) {
        return [];
    }
    
    // Initialize frequency maps
    const pCount = new Map();
    const windowCount = new Map();
    const result = [];
    
    // Count frequencies in p
    for (const c of p) {
        pCount.set(c, (pCount.get(c) || 0) + 1);
    }
    
    // Process first window
    for (let i = 0; i < p.length; i++) {
        windowCount.set(s[i], (windowCount.get(s[i]) || 0) + 1);
    }
    
    // Check first window
    if (mapsEqual(windowCount, pCount)) {
        result.push(0);
    }
    
    // Slide window and check remaining positions
    for (let i = p.length; i < s.length; i++) {
        // Add new character
        windowCount.set(s[i], (windowCount.get(s[i]) || 0) + 1);
        // Remove old character
        const oldChar = s[i - p.length];
        windowCount.set(oldChar, windowCount.get(oldChar) - 1);
        if (windowCount.get(oldChar) === 0) {
            windowCount.delete(oldChar);
        }
        
        // Check if current window is anagram
        if (mapsEqual(windowCount, pCount)) {
            result.push(i - p.length + 1);
        }
    }
    
    return result;
};

function mapsEqual(map1, map2) {
    if (map1.size !== map2.size) {
        return false;
    }
    for (const [key, value] of map1) {
        if (map2.get(key) !== value) {
            return false;
        }
    }
    return true;
}

C# Solution

public class Solution {
    public IList FindAnagrams(string s, string p) {
        if (p.Length > s.Length) {
            return new List();
        }
        
        // Initialize frequency arrays
        int[] pCount = new int[26];
        int[] windowCount = new int[26];
        IList result = new List();
        
        // Count frequencies in p
        foreach (char c in p) {
            pCount[c - 'a']++;
        }
        
        // Process first window
        for (int i = 0; i < p.Length; i++) {
            windowCount[s[i] - 'a']++;
        }
        
        // Check first window
        if (Enumerable.SequenceEqual(windowCount, pCount)) {
            result.Add(0);
        }
        
        // Slide window and check remaining positions
        for (int i = p.Length; i < s.Length; i++) {
            // Add new character
            windowCount[s[i] - 'a']++;
            // Remove old character
            windowCount[s[i - p.Length] - 'a']--;
            
            // Check if current window is anagram
            if (Enumerable.SequenceEqual(windowCount, pCount)) {
                result.Add(i - p.Length + 1);
            }
        }
        
        return result;
    }
}