平衡字符串 c++ || 尺取法

题目
一个长度为 n 的字符串 s，其中仅包含 ‘Q’, ‘W’, ‘E’, ‘R’ 四种字符。
如果四种字符在字符串中出现次数均为 n/4，则其为一个平衡字符串。
现可以将 s 中连续的一段子串替换成相同长度的只包含那四个字符的任意字符串，使其变为一个平衡字符串，问替换子串的最小长度?
如果 s 已经平衡则输出0。

Inuput
一行字符表示给定的字符串s

Outnput
一个整数表示答案

Example
input
QWER
output
0

input
QQWE
output
1

input
QQQW
output
2

input
QQQQ
output
3

Note
1<=n<= 10^5
n是4的倍数
字符串中仅包含字符 ‘Q’, ‘W’, ‘E’ 和 ‘R’.

解题思路
1.数据太大，暴力做法不可取。

2.我们应该每个字符只判断一次，最大程度降低复杂度。

3.使用尺取法，即双指针
一个指针 l 指向区间的左边，另一个指针 r 指向区间右边。
定义一个P(char a)函数,返回对应字母的索引。
首先预处理，把所有字母分别有多少个存入count数组里面。
初始化一个result=c.size（）装结果，并层层比较维护。

4.尺取法过程中，首先判断 r 有没有出界， 然后一个一个的把右区间对应的字母给加入到区间里面 ，并且加入进去后，要把count 维护，因为count 记录的是区间外面的每个字母对应的个数。

5.判断count，如果有大于 n/4 这个要求的，那肯定不符合要求，所以要继续往右移动扩大区间。

6.左区间也不能超过 c.size（） ， 并且 区间满足要求 后，我们要缩小区间，以便达到最小的区间，所以要 l++，并且实时维护count。

代码实现

#include<iostream>
#include<string>
#include<cmath>
using namespace std;

string c;  //用来装字母 
int  l , r ;
int count[4];  //装字母的个数. 0-Q,1-W,2-E,3-R 


int P ( char a)
{
	if( a == 'Q') return 0;
	if( a == 'W') return 1;
	if( a == 'E') return 2;
	if( a == 'R') return 3;
}

int main()
{
	cin>>c;
	for( int i=0; i< c.size() ;i++)
	{
		count[ P(c[i]) ] ++;
	}
	int n = c.size() / 4;
	if( count[0]==n && count[1]==n && count[2]==n&& count[3] ==n )
	{
		cout<<"0"<<endl; return 0;
	}
	
	int result = c.size();  
	while( r < c.size() )  //没有出界 
	{
		count[ P( c[r] ) ]--;  //把右区间的字母给减掉
		bool flag = 1;
		for(int i=0 ; i<4 ;i++) 
		if( count[i] > n)   //外面有大于平均值的 ,我们应该把右框继续往右移 
		{
			flag = 0; break;
		} 
		
	while ( flag == 1 && l < c.size()) 
	{
		count[ P(c[l]) ] ++;    //左边出框的要加回来
		result = min(result , r-l+1);
		if(  count[ P(c[l]) ] > n )    //如果左边的移出去后超过了平均数，则开始移右框 
		 flag = 0;
		 
		 l++;   //左框 右移移 
		}
		r ++ ;	//移右框 
	}
	cout << result<<endl;
	return 0;
}

小结
先移右框，移到合法，然后移动左框，并且不停更新result，直到不合法，然后又开始移动右框，直到结束。