LeetCode — 438. Find All Anagrams in a String

In this blog post, we dive into an effective technique for identifying all anagrams of a given string p within another string s. The method hinges on a fixed-size sliding window combined with a character frequency mapping strategy.

Core Concept and Challenge

First, it revolves around a sliding window mechanism, which maintains a dynamic segment of string s of length equal to p. As we traverse s, we continuously update the count of each letter within this window. The key challenge here is to manage this window’s size always to reflect the current segment of interest in s.

Second, map each lowercase letter to a unique index in an array and use these arrays to count character occurrences. We create two arrays, each with 26 elements (for each letter of the alphabet), where the value at each index represents the frequency of a corresponding letter.

Process

1. Sliding Window Approach:

• We use a sliding window of fixed length, equal to the length of p (pLen). This window traverses over s.
• As we move through s, each letter’s frequency is tracked in an array sArr.
• Crucially, when our index i in s surpasses pLen, we decrease the frequency of the letter that has just moved out of the window (s[i — pLen]).
• This approach ensures our window always contains a segment of s exactly pLen letters long.

2. Character Frequency Mapping:

• Two arrays, each of 26 elements, represent the frequency of each letter for s and p.
• These arrays act as a quick reference to compare the current window in s with p.

3. Identifying Anagrams:

• A match occurs when the frequency array of our window in s (sArr) matches that of p (pArr).
• Each match corresponds to an anagram of p in s.

Complexity Analysis

Time Complexity: O(n), where n is the length of s. Each character in s is examined once.
Space Complexity: O(1), as the size of the arrays for frequency counting is constant and independent of the input size.

JavaScript Version

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function (s, p) {
    // Using a sliding window to traverse the string of s
    // the window length is the length of p
    if (s.length === 0 || p.length === 0) return [];

    let sLen = s.length;
    let pLen = p.length;
    // get letter a' char code to calculate 26 letter index
    let aCharCode = "a".charCodeAt();

    // Map lowercase letters to the index of the array
    // the value being the number of occurrences
    let sArr = new Array(26).fill(0);
    let pArr = new Array(26).fill(0);

    let result = [];

    for (let i = 0; i < pLen; i++) {
        pArr[p[i].charCodeAt() - aCharCode]++;
    }

    // traverse s
    for (let i = 0; i < sLen; i++) {
        sArr[s[i].charCodeAt() - aCharCode]++;

        // Using a sliding window of fixed size pLen in string 's':
        // Add new letters to sArr, and remove the oldest one when the window slides past pLen.
        if (i >= pLen) {
            sArr[s[i - pLen].charCodeAt() - aCharCode]--;
        }

        if (arrayEqual(sArr, pArr)) {
            result.push(i - pLen + 1);
        }
    }
    return result;
};

let arrayEqual = function (sArr, pArr) {
    for (let i = 0; i < sArr.length; i++) {
        if (sArr[i] !== pArr[i]) return false;
    }

    return true;
}

Java Version

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        // Using a sliding window to traverse the string of s
        // the window length is the length of p
        if (s.length() == 0 || p.length() == 0)
            return new ArrayList<>();

        int sLen = s.length();
        int pLen = p.length();

        // Map lowercase letters to the index of the array
        // the value being the number of occurrences
        int[] sArr = new int[26];
        int[] pArr = new int[26];

        List<Integer> result = new ArrayList<>();

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

        for (int i = 0; i < sLen; i++) {
            sArr[s.charAt(i) - 'a']++;

            // Using a sliding window of fixed size pLen in string 's':
            // Add new letters to sArr, and remove the oldest one when the window slides past pLen.
            if (i >= pLen) {
                sArr[s.charAt(i - pLen) - 'a']--;
            }

            // Compare the frequency array of the current window with p's frequency array
            if (Arrays.equals(sArr, pArr)) {
                result.add(i - pLen + 1);
            }
        }

        return result;
    }
}