Find All Anagrams in a String medium

Problem Statement

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".

Steps

1. Character Count Maps: Create two maps (objects in JavaScript) to store the character frequencies: one for the pattern p ( pMap), and one for a sliding window of the same size as p in s (windowMap).

2. Initialization: Initialize pMap by counting the character frequencies in p. Initialize windowMap with the character frequencies of the first window of size p.length in s.

3. Sliding Window: Iterate through s using a sliding window of size p.length. In each iteration:

   • Compare windowMap and pMap. If they are identical, it means an anagram is found, so add the start index of the current window to the result array.
   • Move the window one position to the right. This involves:
     • Removing the character leaving the window from windowMap.
     • Adding the new character entering the window to windowMap.

4. Return Result: Return the array of start indices.

Explanation

The solution uses a sliding window approach along with character frequency maps to efficiently identify anagrams. By comparing character counts instead of directly comparing strings, we avoid unnecessary string comparisons. The use of maps allows for O(1) lookup of character frequencies, optimizing the overall time complexity.

Code

function findAnagrams(s: string, p: string): number[] {
    const result: number[] = [];
    const pMap: { [key: string]: number } = {};
    const windowMap: { [key: string]: number } = {};

    // Initialize pMap
    for (let char of p) {
        pMap[char] = (pMap[char] || 0) + 1;
    }

    let left = 0;
    let right = 0;
    let matched = 0;

    while (right < s.length) {
        const rightChar = s[right];
        windowMap[rightChar] = (windowMap[rightChar] || 0) + 1;

        if (pMap[rightChar] && windowMap[rightChar] === pMap[rightChar]) {
            matched++;
        }

        while (matched === p.length) {
            if (right - left + 1 === p.length) {
                result.push(left);
            }
            const leftChar = s[left];
            windowMap[leftChar]--;
            if (pMap[leftChar] && windowMap[leftChar] < pMap[leftChar]) {
                matched--;
            }
            left++;
        }
        right++;
    }

    return result;
}

Complexity

• Time Complexity: O(n), where n is the length of string s. We iterate through s only once.
• Space Complexity: O(1), because the character set is fixed (26 lowercase English letters). The maps will have a constant size. (In the worst case, it would be O(k) where k is the size of the character set if it's not restricted to lowercase English letters).