LeetCode 1234. 替换子串得到平衡字符串

约 9 分钟
文章信息 6 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 阿里巴巴
标签
字符串 滑动窗口
目录

题目描述

✅ 1234. 替换子串得到平衡字符串

题意分析

字符串只由 Q、W、E、R 四种字符组成，长度是 4 的倍数。「平衡」的定义是四种字符各出现恰好 n / 4 次。允许把某一个连续子串整体替换成任意内容，问这个子串的最小长度。

「只能替换一个连续子串」这个限制是全部难点所在。它意味着答案不是「有多少个字符需要改」，而是「一个能覆盖住所有超额字符的最短区间」。超额的字符可能散落在字符串两端，那么中间不超额的部分也必须被包进去。

「替换成任意内容」这一点则大幅简化了判定：被选中的窗口内的字符可以随便写，所以只要窗口外剩下的字符里，每种字符的出现次数都不超过 n / 4，就一定能把窗口填成平衡的——窗口长度恰好等于四种字符各自缺口之和，填进去即可。于是判定条件完全只看窗口外。

数据规模是 $10^5$，排除枚举所有子串的 $O(n^2)$。而「窗口外每种字符不超过阈值」这个条件具有单调性：窗口越大，窗口外的字符越少，条件越容易满足。这个单调性正是可以用双指针的依据。

边界：字符串本身已经平衡（答案 0）、整个字符串只有一种字符（答案 $3n/4$）、超额字符集中在首尾两端。

解法：滑动窗口维护有效区间

核心思路

暴力做法是枚举所有子串 $[l, r]$，每次统计窗口外的四种字符计数并检查是否都不超过 n / 4，取最短的合法窗口。即使把统计优化成前缀和，枚举本身也是 $O(n^2)$，$10^5$ 下不可行。

瓶颈在于枚举的两个端点是独立移动的。但注意到一个关键的单调性：如果窗口 $[l, r]$ 合法（窗口外全部达标），那么把右端点继续右移得到的 $[l, r+1]$ 一定也合法，因为窗口外的字符只会更少。反过来，固定右端点 r，能让窗口合法的左端点集合是一个前缀 $[0, L_r]$，且 $L_r$ 随 r 单调不减。

这个「$L_r$ 单调不减」就是双指针成立的全部依据：左指针永远不需要回退，两个指针各自单调右移，总移动次数是 $O(n)$。

于是把不变量写清楚：维护计数数组 cnt，它始终表示窗口外（即 [0, left) 与 (right, n-1] 两段之和）中每种字符的出现次数。初始时窗口为空、cnt 是整串的计数；右指针纳入一个字符就把它从 cnt 里减掉（它进了窗口，不再算作窗口外）；左指针弹出一个字符就把它加回 cnt（它离开窗口，重新算作窗口外）。

判定「窗口合法」就是检查 cnt['Q']、cnt['W']、cnt['E']、cnt['R'] 是否都不超过 n / 4。因为只有四种字符，这个检查是 $O(1)$ 的，不需要额外维护「有多少种字符超额」之类的计数器。

求的是最小窗口，所以更新答案的时机是「窗口合法时」，并且要尽可能收缩左端点：每次窗口合法就先记录长度，再把左端点右移一格试着更短，直到窗口不再合法为止。

解题步骤

  • 先统计整串的字符计数 cnt。此时窗口为空，「窗口外」就是整个串，cnt 的初值天然满足不变量。用长度 128 的数组按字符 ASCII 直接索引，比哈希表快且省去装箱。
  • 特判：若四种字符的计数都已不超过 n / 4，直接返回 0。这一步必须有——不是为了性能，而是因为主循环的内层 while 要求 left <= right，空窗口无法在主循环里被表示出来，不特判就会返回 1 而不是 0。
  • answer 初始化为 n（整串必然是一个合法窗口，因为窗口外为空、计数全 0），left = 0。用 n 而不是无穷大，是因为答案上界确定，这样即使后续逻辑有疏漏也不会返回一个荒谬的值。
  • 右指针从 0 遍历到 n-1，每步先执行 cnt[s[right]]--。含义是这个字符进入窗口，从「窗口外」的账上划走，维持不变量。
  • 内层 while 在「left <= right 且四种计数都达标」时循环：先用 right - left + 1 更新 answer，再执行 cnt[s[left]]++ 并 left++。顺序不能反——必须先记录当前这个合法窗口的长度，再收缩；先收缩的话记录的就是收缩后可能已经非法的窗口。
  • 内层用 while 而不是 if，是因为一次右移可能让连续多个左端点都变得可行，必须一直缩到不合法为止才能保证取到当前 right 下的最短窗口。
  • left <= right 这个条件保证窗口至少含一个字符，不会缩成空窗口。空窗口的情形已经被开头的特判处理掉了。
  • 遍历结束返回 answer。

以 s = "QQWE" 走一遍。n = 4，target = 1，初始 cnt 为 Q:2、W:1、E:1、R:0。特判不通过（Q 是 2 超过 1），answer = 4，left = 0。

right = 0，字符 'Q'，cnt['Q'] 减为 1。检查：Q:1、W:1、E:1、R:0 全部不超过 1，窗口 [0,0] 合法。进入内层：answer = min(4, 0-0+1) = 1；把 s[0]='Q' 加回，cnt['Q'] 恢复为 2，left = 1。再判断 left <= right 即 1 <= 0 不成立，退出内层。

right = 1，字符 'Q'，cnt['Q'] 减为 1。检查全部达标，窗口 [1,1] 合法。内层：answer = min(1, 1-1+1) = 1；加回 s[1]='Q'，cnt['Q'] 回到 2，left = 2；2 <= 1 不成立，退出。

right = 2，字符 'W'，cnt['W'] 减为 0。检查：cnt['Q'] 是 2 超过 1，不合法，内层一次都不进。

right = 3，字符 'E'，cnt['E'] 减为 0。cnt['Q'] 仍是 2，不合法。

循环结束返回 1。确实只需把任意一个 Q 替换成 R 即可平衡。

再快速验证特判的必要性：s = "QWER" 时初始计数全为 1，都不超过 target = 1，特判直接返回 0；如果去掉特判走主循环，right = 0 时窗口 [0,0] 合法，answer 会被更新成 1，返回错误答案。

代码实现

// cnt 始终表示「窗口外」的字符计数，窗口合法时先记答案再收缩左端。
class Solution {
    public int balancedString(String s) {
        int n = s.length();
        int target = n / 4;
        int[] cnt = new int[128];
        for (int i = 0; i < n; i++) {
            cnt[s.charAt(i)]++;
        }

        if (cnt['Q'] <= target && cnt['W'] <= target && cnt['E'] <= target && cnt['R'] <= target) {
            return 0;
        }

        int answer = n;
        int left = 0;
        for (int right = 0; right < n; right++) {
            cnt[s.charAt(right)]--;

            while (left <= right
                    && cnt['Q'] <= target && cnt['W'] <= target
                    && cnt['E'] <= target && cnt['R'] <= target) {
                answer = Math.min(answer, right - left + 1);
                cnt[s.charAt(left)]++;
                left++;
            }
        }
        return answer;
    }
}

// cnt 始终表示「窗口外」的字符计数，窗口合法时先记答案再收缩左端。
func balancedString(s string) int {
	n := len(s)
	target := n / 4
	cnt := make([]int, 128)
	for i := 0; i < n; i++ {
		cnt[s[i]]++
	}

	if cnt['Q'] <= target && cnt['W'] <= target && cnt['E'] <= target && cnt['R'] <= target {
		return 0
	}

	answer := n
	left := 0
	for right := 0; right < n; right++ {
		cnt[s[right]]--

		for left <= right && cnt['Q'] <= target && cnt['W'] <= target && cnt['E'] <= target && cnt['R'] <= target {
			if right-left+1 < answer {
				answer = right - left + 1
			}
			cnt[s[left]]++
			left++
		}
	}
	return answer
}

复杂度分析

  • 时间复杂度：$O(n)$，其中 n 为字符串长度。初始统计是一趟 $O(n)$；主循环中右指针总共右移 n 次，左指针在整个过程中只增不减、累计也最多右移 n 次，每次移动伴随一次 $O(1)$ 的计数增减和一次固定四项的达标检查。
  • 空间复杂度：$O(1)$。计数数组长度固定为 128（实际只用到 4 个位置），与输入规模无关；其余只有 left、right、answer、target 几个标量。

关键点总结

  • 「替换一个连续子串使整体满足条件」这类题，判定条件要翻译成对窗口外的约束，而不是对窗口内的约束。一旦转过这个弯，窗口内的内容就完全自由，问题从「怎么改」退化成「区间多长」。
  • 判断能否用双指针，标准是「固定一端后，另一端的可行范围随之单调移动」。本题的单调性来自「窗口变大 ⇒ 窗口外变少 ⇒ 条件更容易满足」，这句话应该在面试中明确说出来，它是复杂度从 $O(n^2)$ 降到 $O(n)$ 的唯一理由。
  • 求最小窗口的模板是「右扩到合法，然后左缩到刚好不合法，收缩前更新答案」；求最大窗口则是「右扩到不合法，左缩到重新合法，收缩后更新答案」。两者的答案更新位置正好相反，混用是这类题最高频的错误来源。
  • 字符集很小时（本题只有 4 种），合法性检查直接写成几个比较即可，$O(1)$；不必上「超额种类计数器」那套优化，反而增加维护成本和出错面。
  • 答案为 0 的情形往往对应空窗口，而空窗口在 left <= right 的框架里无法表示，必须靠前置特判兜住。面试时主动写出这个特判并说明理由，比被面试官用 "QWER" 问住要好。

易错点总结

  • 错误写法：省掉开头「已平衡则返回 0」的特判 → s = "QWER" 时主循环把窗口 [0,0] 判为合法，返回 1，正确答案是 0。
  • 错误写法：内层循环里先 cnt[s[left]]++; left++; 再更新 answer → s = "QQWE" 中 right = 0 时会先把左端点缩到 1，此时窗口为空、right - left + 1 变成 0，answer 被错误地更新成 0。
  • 错误写法：内层用 if 而不是 while → s = "WQQQ" 中，right 到达第二个 Q 时窗口 [0,2] 已合法，还能继续去掉左侧 W 得到长度 2；只收缩一次会返回 3，正确答案是 2。
  • 错误写法：把计数维护成「窗口内」而不是「窗口外」，即右指针 cnt[s[right]]++ → 判定条件的含义整个反了，s = "QQWE" 会因为窗口内 Q 计数超标而永远找不到合法窗口，返回初始值 4。
  • 错误写法：内层条件漏掉 left <= right → s = "QWER" 若没有特判又没有这个守卫，left 会一路超过 right，right - left + 1 变成负数，answer 被更新成负值。
  • 错误写法：左指针移动时忘记 cnt[s[left]]++ 把字符加回窗口外 → s = "QQQQ" 中窗口外的 Q 一旦降到 1 就再也不会回升，窗口会被错误地缩到长度 1；正确答案是 3。
  • 错误写法：answer 初始化为 0 → 循环里用 min 更新永远不会生效，无论输入是什么都返回 0。
  • 错误写法：达标检查只判断 cnt['Q'] <= target → s = "WWWWQQER" 中 Q 已达标但 W 超额，代码会误判整串平衡并返回 0；正确答案是 2。
  • 错误写法：用 n / 4 之外的阈值，比如写成 n / 4 + 1 或用浮点除 → s = "QQWE" 的 target 变成 2，第一轮就判定整串已平衡直接返回 0，正确答案是 1。
  • 错误写法：cnt 数组开成长度 4 并用 s.charAt(i) - 'A' 索引 → 'Q'、'W'、'E'、'R' 相对 'A' 的偏移分别是 16、22、4、17，全部越界。

相似题目

题目 难度 考察点
76. 最小覆盖子串 困难 同为最小窗口，但条件建立在窗口内，需要 valid 计数器
3. 无重复字符的最长子串 中等 求最大窗口，答案更新点在收缩之后而非之前
424. 替换后的最长重复字符 中等 替换次数有上限，需要维护窗口内众数频次做判定
340. 至多包含 K 个不同字符的最长子串 中等 判定量是「不同字符种数」，需在计数归零时同步减种类数