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. Storingp 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 throughs
3. Ati th index ofs check ifp hass[i]
4. inside the if condition create atemp variable which is equal top (this will be used to check by popping out matched character) and a boolean variablecur
5. Now loop throughj which is initially equals toi and less thani + pLen
6. if temp does not contains[j] break out of the loop and change cur tofalse
7. else, pops[j] from temp
8. After for loop check cur, if it's true pushi

Here's the code

varfindAnagrams=function(s,p){letres=newArray()letsLen=s.length,pLen=p.lengthfor(leti=0;i<sLen;i++){if(p.includes(s[i])){lettemp=p,cur=truefor(letj=i;j<i+pLen;j++){if(!temp.includes(s[j])){cur=falsebreak}else{lettempIdx=temp.indexOf(s[j])temp=temp.slice(0,tempIdx)+temp.slice(tempIdx+1)}}if(cur){res.push(i)}}}returnres};

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 ofp in a hash map with value as number of occurences
3. whileend < 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

varfindAnagrams=function(s,p){lethashMap=newMap()for(leti=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)}}letres=newArray()letstart=0,end=0while(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)}}elseif(start==end){start++end++}else{hashMap.set(s[start],hashMap.get(s[start])+1)start++}}returnres};