题目
有一个只含有 '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'四种字符
提交代码
//替换子串得到平衡字符串
//只含四种已定字符
//求替换子串的最小长度
//平衡子串的四种字符的个数都是相等的
//字符串长度确定是4的倍数
//连续一段元素的群体关系
//滑动窗口
//首先遍历字符串，明确四种字符的个数
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
string s;//字符串
int result = (int)(1e5);//结果
int n;//字符串长度
int cnt[4];//四种字符的个数
int m = 0;//需要修改的字符的个数
//判断指针指向的字符是什么
int judge(int p){
if(s[p] == 'Q'){
return 0;
}else if(s[p] == 'W'){
return 1;
}else if(s[p] == 'E'){
return 2;
}else{
return 3;
}
}
//滑动窗口
void slidingWindow(){
int left = 0,right = 0;//左右指针
//int mm = m;//已修改的字符的个数
int c;//标记是哪种字符
int res = 0;//记录子串长度
int t[4];//各字符个数的副本
//复制字符个数副本
copy(begin(cnt),end(cnt),begin(t));
//先单独判断第一个字符
c = judge(left);
if(cnt[c] > n / 4){
t[c]--;
m--;
}
//循环尝试固定左指针
for(;left < n && left <= right;left++){
//移动右指针
while(m > 0 && right < n - 1){
//还未替换完
right++;
//判断新并入的字符是哪一个
c = judge(right);
if(t[c] > n / 4){
//该字符需要替换
m--;
t[c]--;
}else{
t[c]--;
}
}
//当前替换子串长度
if(m == 0){
res = right - left + 1;
result = min(res,result);
}else{
break;
}
//printf("left=%d,right=%d\n",left,right);
//排除最左侧的字符
c = judge(left);
if(cnt[c] > n / 4){
//被替换过
t[c]++;
m++;
if(t[c] <= n / 4){
m = 0;
}
}
//printf("m=%d,res=%d\n",m,res);
}
}
int main(){
//输入整数数组
/*int t;
while(cin.peek() != '\n'){
scanf("%d",&t);
nums1.push_back(t);
}*/
//输入字符串
cin >> s;
//-------------------------------
n = s.size();//字符串长度
//确认四种字符的个数
for(int i = 0;i < n;i++){
if(s[i] == 'Q'){
cnt[0]++;
}else if(s[i] == 'W'){
cnt[1]++;
}else if(s[i] == 'E'){
cnt[2]++;
}else{
cnt[3]++;
}
}
//确定需要修改的次数
for(int i = 0;i < 4;i++){
if(cnt[i] > n / 4){
m += cnt[i] - n / 4;
}
}
if(m == 0 || m == 1){
//特殊情况
result = m;
}else{
//一般情况
//滑动窗口
slidingWindow();
}
//输出结果
printf("%d",result);
return 0;
} 总结
解题思路：替换一个子串其实就是改变一段连续元素的群体关系，故使用滑动窗口（同向双指针）。注意当舍去最左侧元素且该最左侧元素变化了的时候，新生成的子串可能仍成立，因为剩余子串中仍可能含有该元素但是未变。
注意：文章来源：https://www.toymoban.com/news/detail-802706.html
将一个数组的所有元素复制到另一个数组中，可以使用copy(begin(nums1),end(nums1),begin(nums2));文章来源地址https://www.toymoban.com/news/detail-802706.html
到了这里，关于练习题 替换子串得到平衡字符串的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
