What is the best approach for Replace the Substring for Balanced String?

Use a sliding window with two pointers to track counts of characters outside the window, replacing the minimum substring to balance the string.

Why sliding window works for this problem?

Because only the counts outside the current window need to satisfy the n/4 constraint, allowing linear-time substring evaluation.

How do I handle a string that is already balanced?

Check initial frequencies of all characters; if each occurs exactly n/4 times, return 0 immediately.

Can this approach handle very large strings efficiently?

Yes, since it only processes each character at most twice and maintains a fixed-size frequency map, the method scales linearly.

What is the key optimization in Replace the Substring for Balanced String?

Maintaining a running state of character counts outside the window and shrinking the window dynamically to minimize substring length.

#1234

Medium

auto_awesome滑动窗口（状态滚动更新）

LeetCode 题解工作台

替换子串得到平衡字符串

有一个只含有 'Q', 'W', 'E', 'R' 四种字符，且长度为 n 的字符串。假如在该字符串中，这四个字符都恰好出现 n/4 次，那么它就是一个「平衡字符串」。给你一个这样的字符串 s ，请通过「替换一个子串」的方式，使原字符串 s 变成一个「平衡字符串」。你可以用和「待替换子串」长度…

字符串滑动窗口

题目描述

有一个只含有 'Q', 'W', 'E', 'R' 四种字符，且长度为 n 的字符串。

假如在该字符串中，这四个字符都恰好出现 n/4 次，那么它就是一个「平衡字符串」。

给你一个这样的字符串 s，请通过「替换一个子串」的方式，使原字符串 s 变成一个「平衡字符串」。

你可以用和「待替换子串」长度相同的任何其他字符串来完成替换。

请返回待替换子串的最小可能长度。

如果原字符串自身就是一个平衡字符串，则返回 0。

示例 1：

输入：s = "QWER"
输出：0
解释：s 已经是平衡的了。

示例 2：

输入：s = "QQWE"
输出：1
解释：我们需要把一个 'Q' 替换成 'R'，这样得到的 "RQWE" (或 "QRWE") 是平衡的。

示例 3：

输入：s = "QQQW"
输出：2
解释：我们可以把前面的 "QQ" 替换成 "ER"。

示例 4：

输入：s = "QQQQ"
输出：3
解释：我们可以替换后 3 个 'Q'，使 s = "QWER"。

提示：

1 <= s.length <= 10^5
s.length 是 4 的倍数
s 中只含有 'Q', 'W', 'E', 'R' 四种字符

lightbulb

解题思路

方法一：计数 + 双指针

我们先用一个哈希表或数组 cnt 统计字符串 $s$ 中每个字符的数量，如果所有字符的数量都不超过 $n/4$ ，那么字符串 $s$ 就是平衡字符串，直接返回 $0$ 。

否则，我们使用双指针 $j$ 和 $i$ 分别维护窗口的左右边界，初始时 $j = 0$ 。

接下来，从左到右遍历字符串 $s$ ，每次遍历到一个字符，就将该字符的数量减 $1$ ，然后判断当前窗口是否满足条件，即窗口外的字符数量都不超过 $n/4$ 。如果满足条件，那么就更新答案，然后将窗口的左边界右移，直到不满足条件为止。

最后，返回答案即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(C)$ 。其中 $n$ 是字符串 $s$ 的长度；而 $C$ 是字符集的大小，本题中 $C = 4$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def balancedString(self, s: str) -> int:
        cnt = Counter(s)
        n = len(s)
        if all(v <= n // 4 for v in cnt.values()):
            return 0
        ans, j = n, 0
        for i, c in enumerate(s):
            cnt[c] -= 1
            while j <= i and all(v <= n // 4 for v in cnt.values()):
                ans = min(ans, i - j + 1)
                cnt[s[j]] += 1
                j += 1
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n) since each character is processed at most twice while sliding the window. Space complexity is O(1) due to the fixed-size character frequency map for 'Q', 'W', 'E', and 'R'.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate should recognize the need for a sliding window instead of brute-force substring checks.
question_mark
Optimal solutions involve counting characters outside the window, not inside it, to simplify validation.
question_mark
Tracking excess frequencies dynamically is a key optimization for linear-time performance.

warning

常见陷阱

外企场景

error
Forgetting to handle the case when the string is already balanced, returning a non-zero length incorrectly.
error
Incorrectly updating counts when moving the window, leading to invalid balance checks.
error
Assuming replacement must be of specific characters instead of any string of the same length.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Determine maximum substring length that can be replaced without unbalancing the string.
arrow_right_alt
Extend to strings with k distinct characters instead of exactly 4.
arrow_right_alt
Find the minimum replacement substring when balancing requires exactly m occurrences per character instead of n/4.

help

常见问题

外企场景

继续练习

#1208 尽可能使字符串相等 #1297 子串的最大出现次数 #1156 单字符重复子串的最大长度