567. Permutation in String

Problem

Tags: Hash Table, Two Pointers, String, Sliding Window

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^4
• s1 and s2 consist of lowercase English letters.

Code

JS

// 567. Permutation in String (3/22/53726)
// Runtime: 104 ms (72.57%) Memory: 42.36 MB (91.63%) 

/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
function checkInclusion(s1, s2) {
    let s1Map = {};
    for (let i = 0; i < s1.length; i++) s1Map[s1[i]] = (s1Map[s1[i]] || 0) + 1;

    let len = 0;
    let start = 0;
    let win = {};
    for (let i = 0; i < s2.length; i++) {
        let char = s2[i];
        if (!s1Map[char]) {
            start = i + 1;
            win = {};
            len = 0;
            continue;
        }

        win[char] = (win[char] || 0) + 1;
        len++;
        if (s1Map[char] < win[char]) {
            while (s1Map[char] < win[char]) {
                win[s2[start]]--;
                len--;
                start++;
            }
        }
        if (len == s1.length) return true;
    }
    return false;
}