题目链接：1234. 替换子串得到平衡字符串
方法：同向双指针
解题思路
-
若可以通过「替换一个子串」的方式，使原字符串 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)\)。
相同类型题目
// 参考
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;
}
};
// 参考
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;
}
};