438. Find All Anagrams in a String

Description

The problem requires finding all starting indices of substring(s) in a given string s that is an anagram of a given string p. An anagram of a string is another string that contains the same characters, only the order of the characters can be different.

Intuition

To solve this problem, we need to compare substrings of s with the string p. A substring is an anagram of p if the character frequencies in the substring match the frequencies in p. Therefore, the problem reduces to comparing character frequency counts.

Approach

1. Initialization: - Compute the frequency of each character in p and store it in a list pmap. - Initialize a list smap to keep track of the frequency of characters in the current window of size equal to p in s.
2. First Window: - Populate smap with the frequencies of characters in the first window of length p from s.
3. Sliding Window: - Compare smap with pmap. If they are equal, add the starting index of the window to the result list. - Slide the window one character at a time to the right by updating smap: - Add the frequency of the new character coming into the window. - Subtract the frequency of the character leaving the window.
4. Final Check: - After the loop, ensure that the last window (if not already checked) is compared with pmap.
5. Return Results: - Return the list of starting indices where anagrams are found.

Complexity

Time Complexity:

O(n), where n is the length of the string s. The algorithm processes each character in s once, and the frequency comparison is done in constant time since the frequency arrays have a fixed size (26 for lowercase English letters).

Space Complexity:

O(1). The space used for storing frequency counts is constant (26 elements for each frequency array), and the result list's size depends on the number of valid anagrams found.

Code

C++

class Solution {
public:
    vector findAnagrams(string s, string p) {
        vector result;
        if (s.length() < p.length()) {
            return result;
        }

        vector pmap(26, 0);
        vector smap(26, 0);

        for (char c : p) {
            pmap[c - 'a']++;
        }

        for (int i = 0; i < p.length(); i++) {
            smap[s[i] - 'a']++;
        }

        if (smap == pmap) {
            result.push_back(0);
        }

        for (int i = p.length(); i < s.length(); i++) {
            smap[s[i] - 'a']++;
            smap[s[i - p.length()] - 'a']--;

            if (smap == pmap) {
                result.push_back(i - p.length() + 1);
            }
        }

        return result;
    }
};

Python

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        if len(s) < len(p):
            return []

        pmap = [0] * 26
        smap = [0] * 26
        result = []

        for char in p:
            pmap[ord(char) - ord('a')] += 1

        for i in range(len(p)):
            smap[ord(s[i]) - ord('a')] += 1

        if smap == pmap:
            result.append(0)

        for i in range(len(p), len(s)):
            smap[ord(s[i]) - ord('a')] += 1
            smap[ord(s[i - len(p)]) - ord('a')] -= 1

            if smap == pmap:
                result.append(i - len(p) + 1)

        return result

Java

class Solution {
    public List findAnagrams(String s, String p) {
        List result = new ArrayList<>();
        if (s.length() < p.length()) {
            return result;
        }

        int[] pmap = new int[26];
        int[] smap = new int[26];

        for (char c : p.toCharArray()) {
            pmap[c - 'a']++;
        }

        for (int i = 0; i < p.length(); i++) {
            smap[s.charAt(i) - 'a']++;
        }

        if (matches(smap, pmap)) {
            result.add(0);
        }

        for (int i = p.length(); i < s.length(); i++) {
            smap[s.charAt(i) - 'a']++;
            smap[s.charAt(i - p.length()) - 'a']--;

            if (matches(smap, pmap)) {
                result.add(i - p.length() + 1);
            }
        }

        return result;
    }

    private boolean matches(int[] smap, int[] pmap) {
        for (int i = 0; i < smap.length; i++) {
            if (smap[i] != pmap[i]) {
                return false;
            }
        }
        return true;
    }
}

JavaScript

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function(s, p) {
    if (s.length < p.length) {
        return []
    }
    const pmap = new Array(26).fill(0);
    
    for (let i = 0; i < p.length; i++) {
        pmap[p.charAt(i).charCodeAt(0) - 97]++;
        
    }
    const result = [];
    const smap = new Array(26).fill(0);
    for (let i = 0; i  {
    for (let i = 0; i < arr1.length; i++) {
        if (arr1[i] != arr2[i]) {
            return false;
        }
    }

    return true;
}