Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string's permutations is the substring of the second string.

This is similar to Anagrams in string

The algorithm Used in above post works for this problem too, but I am gonna write a slightly different algo.

Input:

s1 = "ab", s2 = "eidbaooo"

Output is **True** because s2 contains one permutation of s1 ("ba")

For this kind of problem all we have to check in a sub string of length s1, whether s2 and s1 has same character frequencies without worrying about the order. like "ab" and "ba" which has same frequency

## Algorithm:

- check whether s1 < s2 (error case)
- create two arrays s1Map and s2Map of length 26 filled with 0 (input is a-z)
- Loop through s1Map and increment s1 ith index based on a = 0 and z = 26
- Also increment s2Map same as above
- initialize count with 0
- Now loop through s1Map and check s1Map[i] == s2Map[i]. if it's equal increment count by 1
- The idea is if count is 26 at any window then permutation exists
- Now loop through s2.length - s1.length
- We return true if count is 26
- create two variables r and l representing right and left
- right will hold the s2[i + s1.length] - 'a' char array index (0 - 26)
- left will hold the s2[i] - 'a' char array index (0 - 26)
- increment s2[r]++
- if s2Map[r] == s1Map[r], we found a match and increment count
- if s2Map[r] == s1Map[r] + 1, there is no match, decrement count
- decrement s2[l]--
- if s2Map[l] == s1Map[l], we found a match, increment count
- else if s2Map[l] == s1Map[l] -1, there is no match, decrement count
- after loop return count == 26

Compare the image with code for better understanding

## Code

```
/**
* @param {string} s1
* @param {string} s2
* @return {boolean}
*/
var checkInclusion = function(s1, s2) {
if(s1.length > s2.length) {
return false
}
let s1Map = new Array(26).fill(0)
let s2Map = new Array(26).fill(0)
for(let i = 0; i < s1.length; i++) {
s1Map[s1.charCodeAt(i) - 'a'.charCodeAt(0)]++
s2Map[s2.charCodeAt(i) - 'a'.charCodeAt(0)]++
}
let count = 0
for(let i = 0; i < 26; i++) {
if(s1Map[i] == s2Map[i]) {
count++
}
}
for(let i = 0; i < s2.length - s1.length; i++) {
if(count == 26) {
return true
}
let r = s2.charCodeAt(i + s1.length) - 'a'.charCodeAt(0)
let l = s2.charCodeAt(i) - 'a'.charCodeAt(0)
s2Map[r]++
if(s2Map[r] == s1Map[r]) {
count++
} else if(s2Map[r] == s1Map[r] + 1) {
count--
}
s2Map[l]--
if(s2Map[l] == s1Map[l]) {
count++
} else if(s2Map[l] == s1Map[l] - 1) {
count--
}
}
return count == 26
};
```

## Top comments (0)