Permutation in String

Problem

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1's permutations is the substring of s2.

Example 1:

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

Example 2:

Input: s1 = "ab", s2 = "eidboaoo"
Output: false

Constraints:

1 <= s1.length, s2.length <= 10⁴
s1 and s2 consist of lowercase English letters.

Solution

/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
var checkInclusion = function(s1, s2) {
    let count = 0; // number of non-zero values in map
    let map = {}; // frequency of characters

    for (const c of s1) { // fill map with characters of s1
        if (!(c in map)) {
            map[c] = 0;
            count++;
        }
        map[c]++;
    }
    let l = 0; // left of window
    let r = 0; // right of window

    for (; r < s2.length; r++) {
        let c = s2[r];
        if (c in map) {
            map[c]--;
        }
        if (map[c] === 0) {
            count--;
        }

        if (!count) { // all values of map are zero
            return true;
        }

        if (r - l + 1 === s1.length) {
            c = s2[l];
            if (map[c] === 0) {
                count++;
            }
            if (c in map) {
                map[c]++;
            }
            l++;
        }
    }
    return false;
};

We will implement a sliding window solution. We initialize map to track the frequency of values in s1, and use a window size of s1.length to slide across s2. In map, we decrement the frequency of values entering the window, and increment the frequency of values leaving the window. This means, if at any point in time, all frequencies in map are 0, it must imply our window is a permutation of s1 (ie. s2[l:r + 1] is a permutation of s1).

Problem​

Solution​

Problem

Solution