Skip to main content

Find All Anagrams in a String

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

Constraints:

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

My solution​

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function(s, p) {
    const dict = new Map();
    const result = [];
    
    for (const char of p) {
        dict.set(char, (dict.get(char) || 0) + 1)
    }
    
    let maxSize = dict.size;
    let left = 0;
    let right = 0;
    
    while (right < s.length) {
        const currentChar = s.charAt(right)
        
        if (dict.has(currentChar)) {
            dict.set(currentChar, dict.get(currentChar) - 1)
        }
        
        if (dict.get(currentChar) === 0) {
            maxSize--
        }
        
        // console.log("maxSize", currentChar, maxSize)
        
        while (maxSize === 0) {
            if (right - left + 1 === p.length) {
                result.push(left)
            }
            
            const leftChar = s.charAt(left)
            if (dict.has(leftChar)) {
                dict.set(leftChar, dict.get(leftChar) + 1)
            }
            if (dict.get(leftChar) > 0) {
                maxSize++
            }
            left++
        }
        
        right++
    }
    
    return result
};