[567] 字符串的排列

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

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

示例1:

输入: s1 = "ab" s2 = "eidbaooo"

输出: True

解释: s2 包含 s1 的排列之一 ("ba").

示例2:

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

输出: False

注意：

输入的字符串只包含小写字母

两个字符串的长度都在 [1, 10,000] 之间

这是一个经典的滑动窗口题型。解题思路可以参考专题中关于双指针滑动窗口的相关介绍。

按照专题中的思路，这里考虑两点：

1. 扩充右边界后，何时能使滑动窗口内的元素满足要求。根据题意，当滑动窗口的长度恰好等于子串长度时，考虑开始缩小左边界。

2. 何时更新返回结果。在本题中，当滑动窗口的hash map与需求子串的hash map完全相同，即互为字母异位词时，此时可以比对并更新结果。这里为了减少遍历比对hash map 的复杂度，多使用了一个valid字段来记录单字符个数匹配的情况。

function checkInclusion(s1: string, s2: string): boolean {
  const needs: Record<string, number> = {};
  for (let i = 0; i < s1.length; i++) {
    const ch = s1[i];
    needs[ch] = needs[ch] ? needs[ch] + 1 : 1;
  }
  const needsCount = Object.keys(needs).length;

  let left = 0,
    right = 0;
  let validCount = 0;
  const window: Record<string, number> = {};

  while (right < s2.length) {
    const ch = s2[right];
    right += 1;

    if (needs[ch]) {
      window[ch] = window[ch] ? window[ch] + 1 : 1;
      if (window[ch] === needs[ch]) validCount += 1;
    }

    while (right - left === s1.length) {
      if (validCount === needsCount) return true;

      const dropCh = s2[left];
      left += 1;

      if (needs[dropCh]) {
        if (window[dropCh] === needs[dropCh]) validCount -= 1;
        window[dropCh] -= 1;
      }
    }
  }
  return false;
}