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:

1. check whether s1 < s2 (error case)
2. create two arrays s1Map and s2Map of length 26 filled with 0 (input is a-z)
3. Loop through s1Map and increment s1 ith index based on a = 0 and z = 26
4. Also increment s2Map same as above
5. initialize count with 0
6. Now loop through s1Map and check s1Map[i] == s2Map[i]. if it's equal increment count by 1
7. The idea is if count is 26 at any window then permutation exists
8. Now loop through s2.length - s1.length
9. We return true if count is 26
10. create two variables r and l representing right and left
11. right will hold the s2[i + s1.length] - 'a' char array index (0 - 26)
12. left will hold the s2[i] - 'a' char array index (0 - 26)
13. increment s2[r]++
14. if s2Map[r] == s1Map[r], we found a match and increment count
15. if s2Map[r] == s1Map[r] + 1, there is no match, decrement count
16. decrement s2[l]--
17. if s2Map[l] == s1Map[l], we found a match, increment count
18. else if s2Map[l] == s1Map[l] -1, there is no match, decrement count
19. 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
};