Find All Anagrams in a String - LeetCode

Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.

Example:

1. s = "cbaebabacd", p = "abc"
2. s = "abab", p ="ab"

This problem looks like basic looping and checking whether the sub array of s contains p, But the problem is p's length is greater than 20000, which will result in Time Limit Exceeded(TLE)

I will go through two approaches

1. Basic looping and checking
2. Storing p in a hashMap and using sliding window technique

Basic Looping and checking Algorithm

1. Create a result array and store length of s and p strings in variables
2. Now Loop through s
3. At i th index of s check if p has s[i]
4. inside the if condition create a temp variable which is equal to p (this will be used to check by popping out matched character) and a boolean variable cur
5. Now loop through j which is initially equals to i and less than i + pLen
6. if temp does not contain s[j] break out of the loop and change cur to false
7. else, pop s[j] from temp
8. After for loop check cur, if it's true push i

Here's the code

var findAnagrams = function(s, p) {
    let res = new Array()
    let sLen = s.length, pLen = p.length
    for(let i = 0; i< sLen; i++) {
        if(p.includes(s[i])) {
            let temp = p, cur = true
            for(let j = i; j < i + pLen; j++) {
                if(!temp.includes(s[j])) {
                    cur = false
                    break
                } else {
                    let tempIdx = temp.indexOf(s[j])
                    temp = temp.slice(0, tempIdx) + temp.slice(tempIdx + 1)
                }
            }
            if(cur) {
                res.push(i)
            }
        }
    }
    return res
};

In the above algorithm we are almost constantly looping through every index of s checking anagram of p exists or not

Sliding Window Technique

This technique id used mostly on strings, arrays, linked lists (basically iterables) and you need to find min, max, or contains

If you observe we are asked to check s contains anagrams of p

So Here's the algorithm:

1. Create two variables start and end
2. First store all the characters of p in a hash map with value as number of occurences
3. while end < s.length

4. if hashMap of s[end] is greater than 0, subtract 1 from it and increase end
   inside the same if check end - start is equal to pLen

   if it's pLen, push start to result array

5. else if start equals to end increment both start and end

6. else increment start and add 1 to hashMap of s[start]

Here's the code

var findAnagrams = function(s, p) {
    let hashMap = new Map()
    for(let i = 0; i < p.length; i++) {
        if(hashMap.has(p[i])) {
            hashMap.set(p[i], hashMap.get(p[i]) + 1)
        } else {
            hashMap.set(p[i], 1)
        }
    }

    let res = new Array()
    let start = 0, end = 0
    while(end < s.length) {
        if(hashMap.get(s[end]) > 0) {
            hashMap.set(s[end], hashMap.get(s[end]) - 1)
            end++
            if(end - start == p.length) {
                res.push(start)
            }
        } else if(start == end) {
            start++
            end++
        } else {
            hashMap.set(s[start], hashMap.get(s[start]) + 1)
            start++
        }
    }
    return res
};