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

方法：同向双指针

解题思路

若可以通过「替换一个子串」的方式，使原字符串 s 变成一个「平衡字符串」，则说明子串外任意字符的数量 $s ≤ n / 4$，否则一旦有一个字符的数量大于 $n / 4$，那么不论如何替换，必定有另一个字符的数量小于 $n / 4$，无法达到平衡。
可以通过同向双指针，初始化 $left = 0，right = 0$，枚举右指针 $right ++$，当 $[left, right]$ 子串外满足字符数量均小于 $n / 4$，则可以替换该子串以达到平衡，此时开始枚举左指针 $left ++ $，若新子串满足上述要求，则同样可以替换该子串。遇到可以替换的子串时，取子串数量最小的更新 $ans$。
$right$ 单调增加不会漏掉答案的保证：若 $[left, right]$ 子串不满足要求，那么 $[left + 1, right], [left + 2, right],...$子串一定不满足，因为 $[left, right]$ 不满足说明子串外一定有某一字符的数量大于 $n / 4$，如果此时再 $left ++$ ，那么只会使得子串外的字符数量增加，更不会符合条件。因此只有先枚举 $right$ 指针使得 $[left, right]$ 子串满足要求之后，再枚举 $left$ 指针来缩短子串长度。

代码

class Solution {
public:
    int balancedString(string s) {
        int n = s.size(), m = n >> 2;
        int cnt['Z']{};
        for (char &ch : s) cnt[ch] ++ ;
        if (cnt['Q'] == m && cnt['W'] == m && cnt['E'] == m && cnt['R'] == m) return 0;
        int ans = n; // INF
        for (int right = 0, left = 0; right < n; right ++ ) {
            cnt[s[right]] -- ;
            while (cnt['Q'] <= m && cnt['W'] <= m && cnt['E'] <= m && cnt['R'] <= m) {
                ans = min(ans, right - left + 1);
                cnt[s[left]] ++ ; left ++ ;
            }
        }
        return ans;
    }
};

复杂度分析

时间复杂度：$O(n)$；
空间复杂度：$O(1)$。

相同类型题目

713. 乘积小于 K 的子数组

// 参考
class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if (k <= 1) return 0;
        int ans = 0, prod = 1;
        for (int left = 0, right = 0; right < nums.size(); right ++ ) {
            prod *= nums[right];
            while (prod >= k) 
                prod /= nums[left ++ ];  
            ans += right - left + 1;
        }
        return ans;
    }
};

209. 长度最小的子数组

// 参考
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        int left = 0, sum = 0, ans = n + 1;
        for (int right = 0; right < n; right ++ ) {
            sum += nums[right];
            while (sum >= target) {
                ans = min(ans, right - left + 1);
                sum -= nums[left ++ ];
            }
        }
        return ans <= n ? ans : 0;
    }
};