Permutation in string - LeetCode

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