567. 字符串的排列

[chasingsnail]

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。

换句话说，第一个字符串的排列之一是第二个字符串的子串。

示例1:

输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").

示例2:

输入: s1= "ab" s2 = "eidboaoo"
输出: False

注意：

输入的字符串只包含小写字母
两个字符串的长度都在 [1, 10,000] 之间

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutation-in-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

当窗口内子串覆盖了 s1 所含所有字符时，收窄 left，当 right - left === s1.length 时，满足了 s1 的排列是 s2 子串的条件，此时返回结果 true。

/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
var checkInclusion = function(s1, s2) {
    let result = false
    
    let freq = {}
    for (const item of s1) {
        freq[item] = freq[item] ? ++freq[item] : 1
    }

    const nLen = Object.keys(freq).length

    let left = 0
    let right = 0
    let matchCount = 0
    while (right < s2.length) {
        const curR = s2[right]
        right++
        if (--freq[curR] === 0) {
            matchCount++
        }
        while (matchCount === nLen) {
            if (right - left === s1.length) {
                return true
            }
            const curL = s2[left]
            left++
            if (++freq[curL] > 0) {
                matchCount--
            }
        }
    }

    return result
};