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

Example:

- s = "cbaebabacd", p = "abc"
- 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

- Basic looping and checking
- Storing
*p*in a hashMap and using sliding window technique

## Basic Looping and checking Algorithm

- Create a result array and store length of s and p strings in variables
- Now Loop through
*s* - At
*i*th index of*s*check if*p*has*s[i]* - 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* - Now loop through
*j*which is initially equals to*i*and less than*i + pLen* - if temp does not contain
`s[j]`

break out of the loop and change cur to`false`

- else, pop
`s[j]`

from temp - 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:

- Create two variables start and end
- First store all the characters of
*p*in a hash map with value as number of occurences - while
*end < s.length* -
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 pLenif it's pLen, push start to result array

else if start equals to end increment both start and end

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
};
```

## Top comments (0)