LeetCode题解：1234. 替换子串得到平衡字符串，滑动窗口，详细注释

[chencl1986]

原题链接：
https://leetcode.cn/problems/replace-the-substring-for-balanced-string/

解题要点：

1. 我们从字符串中截取一部分m，只要剩下的部分每个字符的数量都小于n / 4，就表示s能够通过替换m个字符，变为“平衡字符串”
2. 使用两个指针left和right，将两者之间长度为right - left + 1的字符串当做一个窗口，即可在s中截取出长度为m的字符串
3. 窗口的右边界right从0开始一直移动到n - 1位置，左边界left跟随right移动，查找合适的窗口
4. 当窗口移动到最右侧时，例如s = "QQWQQEQR"，窗口到最右侧时，left = 4; right = 7，此时在窗口中的字符串为QEQR，窗口即使继续向右移动，也无法满足上述条件，直接退出循环即可

解题思路：

1. 先用map统计字符串s中各个字符的数量
2. 如果QWER中每个字符的数量都是n / 4，表示s就是“平衡字符串”
3. 创建left和right指针，right从左向右移动，同时left <= right
4. 每次right向右移动一位，就将map[s[right]]的数量减一，表示有字符移入窗口
5. 每次left向左移动一位，就将map[s[left++]]加一，表示有字符移出窗口
6. 每次移入移出操作后，map中剩下的字符，就是窗口外的字符数量，因此只要判断QWER的数量是否小等于n / 4即可

/**
 * @param {string} s
 * @return {number}
 */
var balancedString = function(s) {
  // 实用map统计当前字符串s中各个字符的数量
  let map = {
    'Q': 0,
    'W': 0,
    'E': 0,
    'R': 0,
  }

  // 统计各个字符的数量
  for (const c of s) {
    map[c]++
  }

  const n = s.length
  // 计算如果是平衡字符串，每个字符的数量
  const target = n / 4

  // 如果每个字符的数量都为n / 4，s为平衡字符串
  if (
    map.Q === target &&
    map.W === target &&
    map.E === target &&
    map.R === target
  ) {
    return 0
  }

  // 缓存结果，最大值为n - 1，初始值大于等于n - 1即可
  let result = n - 1

  // 实用两个指针，从字符串中截取一个范围
  for (let left = 0, right = 0; right < n; right++) {
    // 每次滑入窗口一个字符，就将其数量减一
    map[s[right]]--

    // 字符串中除了窗口以外的部分，每个字符的数量都小等于target
    // 就意味着字符串能够通过变换right - left + 1个字符，成为“平衡字符串”
    while (
      // 左指针必须小等于右指针，才能形成窗口
      left <= right &&
      // 查看窗口以外的字符，数量是否都小于target
      map.Q <= target &&
      map.W <= target &&
      map.E <= target &&
      map.R <= target
    ) {
      // 在所有结果中取最小值
      result = Math.min(result, right - left + 1)
      // 每次查找完之后，窗口要向右移动
      // 同时会有一个字符被移出窗口，需要将它的数量加一
      map[s[left++]]++
    }
  }

  return result
};