Find All Anagrams in a String（找到字符串中所有字母异位词）

题目 / Problem

中文： 给定两个字符串 s 和 p，返回 s 中所有 p 的字母异位词子串的起始下标。答案可以按任意顺序返回。

字母异位词包含完全相同的字符及出现次数，只是字符排列顺序可能不同。

English: Given two strings s and p, return an array containing the starting indices of all anagrams of p in s. The answer may be returned in any order.

Anagrams contain exactly the same characters with the same frequencies, possibly in a different order.

示例 / Examples

Example 1

Input:  s = "cbaebabacd", p = "abc"
Output: [0,6]

• 从下标 0 开始的子串是 "cba"，它是 "abc" 的字母异位词。
  The substring starting at index 0 is "cba", an anagram of "abc".
• 从下标 6 开始的子串是 "bac"，它也是 "abc" 的字母异位词。
  The substring starting at index 6 is "bac", also an anagram of "abc".

Example 2

Input:  s = "abab", p = "ab"
Output: [0,1,2]

s[0...2) = "ab"
s[1...3) = "ba"
s[2...4) = "ab"

三个长度为 2 的子串都包含一个 'a' 和一个 'b'。
All three length-2 substrings contain one 'a' and one 'b'.

约束 / Constraints

• 1 <= s.length, p.length <= 3 × 10^4
• s 和 p 只包含小写英文字母。
  s and p consist only of lowercase English letters.

核心观察 / Key Observation

p 的字母异位词长度一定等于 p.length。因此只需要检查 s 中所有长度固定为 p.length 的窗口。
Every anagram of p has length p.length. Therefore, only fixed-size windows of that length in s need to be checked.

s = "cbaebabacd", p.length = 3

"cba" → "bae" → "aeb" → ... → "bac" → "acd"

相邻窗口只相差两个字符：左侧移出一个字符，右侧移入一个字符。使用滑动窗口可以增量更新字符计数，不必重新统计整个子串。
Adjacent windows differ by only two characters: one leaves from the left and one enters from the right. A sliding window updates frequencies incrementally instead of recounting every substring.

解题思路：固定长度滑动窗口 / Approach: Fixed-Size Sliding Window

使用长度为 26 的数组 counts 表示每个字符还需要多少个：
Use an array counts of length 26 to represent how many more of each character are needed:

1. 遍历 p，增加对应字符的需求数量。
   Traverse p and increase the required count for each character.
2. 使用 left 和 right 维护 s 中的滑动窗口。
   Use left and right to maintain a sliding window in s.
3. 字符从右侧进入时，减少它在 counts 中的数量。
   When a character enters from the right, decrease its count.
4. 窗口超过 p.length 时，让最左字符离开并恢复它的计数。
   When the window grows beyond p.length, remove the leftmost character and restore its count.
5. 当窗口长度等于 p.length，并且所有所需字符都已匹配时，记录 left。
   When the window length equals p.length and all required characters are matched, record left.

remaining 的含义 / Meaning of remaining

remaining 表示还需要匹配多少个字符，初始值为 p.length。
remaining is the number of required character occurrences still unmatched. It starts at p.length.

当字符进入窗口时：
When a character enters the window:

if (counts[index] > 0) {
  remaining--;
}

counts[index]--;

• 如果 counts[index] > 0，说明当前字符满足了一个尚未匹配的需求，所以 remaining--。
  If counts[index] > 0, this occurrence satisfies an unmet requirement, so decrement remaining.
• 如果 counts[index] <= 0，说明窗口中该字符已经足够或过多，它不减少 remaining。
  If counts[index] <= 0, the window already has enough of that character, so remaining does not decrease.

当字符离开窗口时，在恢复计数之前检查：
When a character leaves, check before restoring its count:

if (counts[index] >= 0) {
  remaining++;
}

counts[index]++;

如果 counts[index] >= 0，离开的字符原本贡献了一个有效匹配，现在又缺少一个，所以 remaining++。
If counts[index] >= 0, the leaving occurrence had contributed to a valid match, so one required character becomes unmatched and remaining increases.

JavaScript 实现 / JavaScript Implementation

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
function findAnagrams(s, p) {
  if (p.length > s.length) {
    return [];
  }

  const counts = new Array(26).fill(0);

  for (const character of p) {
    const index = character.charCodeAt(0) - 97;
    counts[index]++;
  }

  const result = [];
  let left = 0;
  let remaining = p.length;

  for (let right = 0; right < s.length; right++) {
    const enteringIndex = s.charCodeAt(right) - 97;

    if (counts[enteringIndex] > 0) {
      remaining--;
    }
    counts[enteringIndex]--;

    // 保持窗口长度不超过 p.length
    // Keep the window length at most p.length
    if (right - left + 1 > p.length) {
      const leavingIndex = s.charCodeAt(left) - 97;

      if (counts[leavingIndex] >= 0) {
        remaining++;
      }
      counts[leavingIndex]++;
      left++;
    }

    if (right - left + 1 === p.length && remaining === 0) {
      result.push(left);
    }
  }

  return result;
}

执行过程 / Walkthrough

以 s = "cbaebabacd"、p = "abc" 为例：
For s = "cbaebabacd" and p = "abc":

p 的需求 / Required counts:
a: 1, b: 1, c: 1

最终返回 [0,6]。
The final result is [0,6].

为什么窗口必须固定长度？ / Why Must the Window Have Fixed Length?

即使某个较长窗口包含了 p 所需的所有字符，它也不是 p 的字母异位词，因为它包含额外字符。
Even if a longer window contains every character required by p, it is not an anagram because it contains extra characters.

因此只有同时满足以下两个条件时才能记录答案：
Record an answer only when both conditions hold:

窗口长度 === p.length
window length === p.length

remaining === 0

与重新计数对比 / Comparison with Recounting

如果对每个起点都重新统计长度为 p.length 的子串，需要约 O(s.length × p.length) 时间。
Recounting every length-p.length substring takes roughly O(s.length × p.length) time.

滑动窗口只处理每个字符进入和离开各一次，将时间降低到线性。
The sliding window processes each character once when entering and once when leaving, reducing the runtime to linear.

复杂度 / Complexity

设 n = s.length，m = p.length。
Let n = s.length and m = p.length.

• 时间复杂度 / Time: O(n + m)
• 空间复杂度 / Space: O(1)，计数数组长度固定为 26；不包括返回结果。
  O(1) because the frequency array always has length 26, excluding output.

易错点 / Common Pitfalls

• 字母异位词必须具有与 p 相同的长度和字符频率。
  An anagram must have the same length and character frequencies as p.
• 当 p.length > s.length 时，应立即返回 []。
  Return [] immediately when p.length > s.length.
• 字符进入窗口时先判断 counts[index] > 0，再执行减一。
  When a character enters, test counts[index] > 0 before decrementing it.
• 字符离开窗口时先判断 counts[index] >= 0，再执行加一。
  When a character leaves, test counts[index] >= 0 before incrementing it.
• 记录的是窗口起点 left，不是右指针 right。
  Record the window start left, not the right pointer right.
• 题目只包含小写英文字母，因此可以用字符编码减去 97 映射到下标 0-25。
  Since inputs contain only lowercase letters, subtract character code 97 to map them to indices 0-25.