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.

如果 s1 的排列之一是 s2 的子字串，则传回 true。

Example 1

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

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

Step

先将 s1 字串中的 chart 建立一个 hash table

将 s2 字串以 s1 长度为基準将 s2 的 chart 也建立 hash table

可以看到 s2 的 hash table 中的内容和 s1 hash table 中的不一样，所以 sliding window 往右边移动一格（移除 s2 的 index = 0 并加入 s2 的 index = 4）

继续比对，s2 的 hash table 中的内容和 s1 hash table 中的不一样，所以 sliding window 往右边移动一格（移除 s2 的 index = 1 并加入 s2 的 index = 5）

继续比对，s2 的 hash table 中的内容和 s1 hash table 中的不一样，所以 sliding window 往右边移动一格（移除 s2 的 index = 2 并加入 s2 的 index = 6）

继续比对，s2 的 hash table 中的内容和 s1 hash table 中的不一样，所以 sliding window 往右边移动一格（移除 s2 的 index = 3 并加入 s2 的 index = 7）

现在 s2 的 hash table 中的内容和 s1 hash table 中的一样，于是回传 true。

Coding

/** * @param {string} s1 * @param {string} s2 * @return {boolean} */var checkInclusion = function(s1, s2) {    const hash = new Map();    for (let i = 0; i < s1.length; i++) {        if (!hash.has(s1[i])) hash.set(s1[i], 1);        else hash.set(s1[i], hash.get(s1[i]) + 1);    }    let l = 0, r = 0;    const s2Hash = new Map();    while (r < s2.length) {        let range = r - l + 1;        if (!s2Hash.has(s2[r])) s2Hash.set(s2[r], 1);        else s2Hash.set(s2[r], s2Hash.get(s2[r]) + 1);        if (range === s1.length) {            let match = true            for (const [key, count] of hash.entries()) {                if (!s2Hash.has(key) || s2Hash.get(key) !== count) match = false            }            if (match) {                return true            }            const lItem = s2Hash.get(s2[l]) - 1;            if (lItem === 0) s2Hash.delete(s2[l]);            else s2Hash.set(s2[l], lItem);            l++;        }        r++;    }    return false;};

Time complexity: O(n)