练习题 替换子串得到平衡字符串

题目

有一个只含有?'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;
} 

总结

解题思路：替换一个子串其实就是改变一段连续元素的群体关系，故使用滑动窗口（同向双指针）。注意当舍去最左侧元素且该最左侧元素变化了的时候，新生成的子串可能仍成立，因为剩余子串中仍可能含有该元素但是未变。

注意：

? ? ? ? 将一个数组的所有元素复制到另一个数组中，可以使用copy(begin(nums1),end(nums1),begin(nums2));