[438] 找到字符串中所有字母异位词

给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

说明：

字母异位词指字母相同，但排列不同的字符串。

不考虑答案输出的顺序。

示例 1:

输入:

s: "cbaebabacd" p: "abc"

输出:

[0, 6]

解释:

起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。

起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。

示例 2:

输入:

s: "abab" p: "ab"

输出:

[0, 1, 2]

解释:

起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。

起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。

起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。

这道题与 [567] 字符串的排列 的解法几乎完全一致，只是一个返回boolean，一个返回索引而已。因为所谓的字母异位词实际上就是相同字符串的不同排列而已。

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

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

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

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

function findAnagrams(s: string, p: string): number[] {
  const res: number[] = [];

  const needs: Record<string, number> = {};
  for (let i = 0; i < p.length; i++) {
    const ch = p[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 < s.length) {
    const ch = s[right];
    right += 1;

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

    while (right - left === p.length) {
      if (validCount === needsCount) res.push(left);

      const dropCh = s[left];
      left++;

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

  return res;
}