Find All Anagrams in a String - LeetCode
Tags: hashtable, slidingwindow
Published: 2020-05-18 03:06:26

---
title: Find All Anagrams in a String - LeetCode
published: true
description: LeetCode medium problem
tags: hash-table, sliding-window
---

# 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

```js
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]


![Find all anagrams in a string](https://i.imgur.com/gi83Lom.png)

Here's the code

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