Medium

题目描述

给你一个长度为 n 的字符串 s ，其中仅含有 4 种字符：‘Q’、‘W’、‘E’ 和 ‘R’。

如果一个字符串的每个字符在其中都恰好出现 n / 4 次，那么该字符串就是平衡的。其中 n 是字符串的长度。

返回使 s 平衡所需替换的最小子串长度。如果 s 已经平衡，则返回 0。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • n == s.length
  • 4 <= n <= 10^5
  • n 是 4 的倍数
  • s 仅含有 ‘Q’、‘W’、‘E’ 和 ‘R’ 四种字符

提示：

  • 使用双指针算法确保双指针外的所有字符数量都小于或等于 n/4
  • 这意味着你需要统计每个字母的数量并确保数量足够

解题思路

这道题的核心思路是使用滑动窗口（双指针）来找到最小的需要替换的子串。

分析过程：

首先理解题目：我们需要让每个字符都出现 n/4 次。如果某个字符出现次数超过 n/4，那么多出来的部分必须被替换掉。

关键观察： 如果我们能找到一个窗口，使得窗口外的每个字符数量都不超过 n/4，那么我们就可以通过替换窗口内的字符来达到平衡。

算法步骤：

  1. 统计每个字符的出现次数，计算每个字符需要减少的数量
  2. 如果所有字符都不需要减少，说明已经平衡，返回 0
  3. 使用滑动窗口，维护窗口外每个字符的数量
  4. 当窗口外所有字符数量都不超过 n/4 时，当前窗口就是一个可行解
  5. 不断收缩左边界来寻找最小窗口

时间复杂度分析： 双指针最多遍历字符串两次，所以是 O(n)。 空间复杂度分析： 只需要常数空间存储字符计数，所以是 O(1)。

代码实现

class Solution {
public:
    int balancedString(string s) {
        int n = s.length();
        int target = n / 4;
        
        // 统计每个字符出现次数
        unordered_map<char, int> count;
        for (char c : s) {
            count[c]++;
        }
        
        // 计算需要减少的字符数量
        unordered_map<char, int> need;
        for (char c : {'Q', 'W', 'E', 'R'}) {
            need[c] = max(0, count[c] - target);
        }
        
        // 如果已经平衡，返回0
        if (need['Q'] == 0 && need['W'] == 0 && need['E'] == 0 && need['R'] == 0) {
            return 0;
        }
        
        int left = 0, right = 0;
        int minLen = n;
        unordered_map<char, int> window;
        
        while (right < n) {
            window[s[right]]++;
            
            // 当窗口包含了足够多需要替换的字符时，尝试收缩左边界
            while (window['Q'] >= need['Q'] && window['W'] >= need['W'] && 
                   window['E'] >= need['E'] && window['R'] >= need['R']) {
                minLen = min(minLen, right - left + 1);
                window[s[left]]--;
                left++;
            }
            
            right++;
        }
        
        return minLen;
    }
};

class Solution:
    def balancedString(self, s: str) -> int:
        n = len(s)
        target = n // 4
        
        # 统计每个字符出现次数
        count = {}
        for c in s:
            count[c] = count.get(c, 0) + 1
        
        # 计算需要减少的字符数量
        need = {}
        for c in 'QWER':
            need[c] = max(0, count.get(c, 0) - target)
        
        # 如果已经平衡，返回0
        if all(need[c] == 0 for c in 'QWER'):
            return 0
        
        left = 0
        min_len = n
        window = {}
        
        for right in range(n):
            window[s[right]] = window.get(s[right], 0) + 1
            
            # 当窗口包含了足够多需要替换的字符时，尝试收缩左边界
            while all(window.get(c, 0) >= need[c] for c in 'QWER'):
                min_len = min(min_len, right - left + 1)
                window[s[left]] = window.get(s[left], 0) - 1
                left += 1
        
        return min_len

public class Solution {
    public int BalancedString(string s) {
        int n = s.Length;
        int target = n / 4;
        
        // 统计每个字符出现次数
        Dictionary<char, int> count = new Dictionary<char, int>();
        foreach (char c in s) {
            count[c] = count.GetValueOrDefault(c, 0) + 1;
        }
        
        // 计算需要减少的字符数量
        Dictionary<char, int> need = new Dictionary<char, int>();
        foreach (char c in "QWER") {
            need[c] = Math.Max(0, count.GetValueOrDefault(c, 0) - target);
        }
        
        // 如果已经平衡，返回0
        if (need['Q'] == 0 && need['W'] == 0 && need['E'] == 0 && need['R'] == 0) {
            return 0;
        }
        
        int left = 0;
        int minLen = n;
        Dictionary<char, int> window = new Dictionary<char, int>();
        
        for (int right = 0; right < n; right++) {
            window[s[right]] = window.GetValueOrDefault(s[right], 0) + 1;
            
            // 当窗口包含了足够多需要替换的字符时，尝试收缩左边界
            while (window.GetValueOrDefault('Q', 0) >= need['Q'] && 
                   window.GetValueOrDefault('W', 0) >= need['W'] && 
                   window.GetValueOrDefault('E', 0) >= need['E'] && 
                   window.GetValueOrDefault('R', 0) >= need['R']) {
                minLen = Math.Min(minLen, right - left + 1);
                window[s[left]] = window.GetValueOrDefault(s[left], 0) - 1;
                left++;
            }
        }
        
        return minLen;
    }
}

var balancedString = function(s) {
    const n = s.length;
    const target = n / 4;
    
    // 统计每个字符出现次数
    const count = {};
    for (const c of s) {
        count[c] = (count[c] || 0) + 1;
    }
    
    // 计算需要减少的字符数量
    const need = {};
    for (const c of 'QWER') {
        need[c] = Math.max(0, (count[c] || 0) - target);
    }
    
    // 如果已经平衡，返回0
    if (need['Q']
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)双指针遍历字符串，每个字符最多被访问两次
空间复杂度O(1)只需要常数空间存储字符计数，因为字符集大小固定为4