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

2024-08-15
福建
本文字数：1159 字
阅读完需：约 4 分钟

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

解题要点：

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

解题思路：

先用map统计字符串s中各个字符的数量
如果QWER中每个字符的数量都是n / 4，表示s就是“平衡字符串”
创建left和right指针，right从左向右移动，同时left <= right
每次right向右移动一位，就将map[s[right]]的数量减一，表示有字符移入窗口
每次left向左移动一位，就将map[s[left++]]加一，表示有字符移出窗口
每次移入移出操作后，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};