平衡字符串问题

题意：
一个长度为 n 的字符串 s，其中仅包含 ‘Q’, ‘W’, ‘E’, ‘R’ 四种字符。
如果四种字符在字符串中出现次数均为 n/4，则其为一个平衡字符串。
现可以将 s 中连续的一段子串替换成相同长度的只包含那四个字符的任意字符串，使其变为一个平衡字符串，问替换子串的最小长度?
如果 s 已经平衡则输出0。
输入：
一行字符表示给定的字符串s，1<=n<=10^5，n是4的倍数，字符串中仅包含字符 ‘Q’, ‘W’, ‘E’ 和 ‘R’。
输出：
一个整数表示答案
输入样例：
QQQW
输出样例：
2
解题思路：
尺取法的应用，需要两个指针l和r，初始时均在字符数组的头部，当当前区间是满足要求的区间时，用r-l+1更新答案，且l自增一，若l和r相等，则l和r均自增一。当前区间并不满足要求时，r自增一，直到r超过整个区间右端点。判断一个区间是否满足条件的方法是：用 sum1, sum2, sum3, sum4 分别记录不包含区间 [L, R]这一段时，字符 ‘Q’, ‘W’, ‘E’, ‘R’ 的个数，先通过替换使 4 类字符数量一致，再判断剩余空闲位置是否 为 4 的倍数，MAX = max(sum1, sum2, sum3, sum4)，TOTAL=R–L+1，FREE = TOTAL - [(MAX-sum1)+(MAX-sum2)+(MAX-sum3)+(MAX-sum4)]，若 FREE ≥ 0 且为 4 的倍数，则满足要求;否则不满足。
注意事项：
1、字符读入可以用string类型直接cin，也可以定义字符型数组，n=0;while(scanf("%c",&a[n])!=EOF) n++;
2、注意单独判断若一开始字符串就平衡应该直接输出0后return。
3、若每次check一个区间是否满足要求时都遍历计算四个字符的个数很容易超时，可以定义全局变量s1,s2,s3,s4来实时记录四个字符的个数，注意在需要时即使对s1,s2,s3,s4的值分别进行更新，可以使得每次check的速度更快。
总结：
应用双指针的思想来遍历数组的区间是重要的技巧。这类问题一般所求解答案为一个连续区间，且区间左右端点移动有明确方向，当前 [L, R] 满足要求，则 L++，当前 [L, R] 不满足要求，则 R++。
参考代码：

#include <iostream>
#include <string>
using namespace std;
char a[100005];
int n;
int s1=0,s2=0,s3=0,s4=0;// Q W E R
int mymax(int s1,int s2,int s3,int s4){
    int i=s1>s2 ? s1:s2;
    int j=s3>s4 ? s3:s4;
    return i>j ? i:j;
}
bool check(int x,int y){
    int m=mymax(s1, s2, s3, s4);
    int t=y-x+1;
    int f=t-(4*m-s1-s2-s3-s4);
    if(f>=0&&f%4==0)return true;
    else return false;
}
int main(int argc, const char * argv[]) {
    n=0;while(scanf("%c",&a[n])!=EOF) n++;
    int ans=n;
    for (int i=0; i<n; i++) {
        if(a[i]=='Q')s1++;
        if(a[i]=='W')s2++;
        if(a[i]=='E')s3++;
        if(a[i]=='R')s4++;
    }
    if(s1==n/4&&s2==n/4&&s3==n/4&&s4==n/4){
        cout<<0<<endl;
        return 0;
    }
    int l=0;
    int r=0;
    if(a[0]=='Q')s1--;
    if(a[0]=='W')s2--;
    if(a[0]=='E')s3--;
    if(a[0]=='R')s4--;
    while (r<n) {
        if(check(l, r)){
            if(r-l+1<ans)ans=r-l+1;
            if(l==r){
                r++;
                if(a[r]=='Q')s1--;
                if(a[r]=='W')s2--;
                if(a[r]=='E')s3--;
                if(a[r]=='R')s4--;
            }
            if(a[l]=='Q')s1++;
            if(a[l]=='W')s2++;
            if(a[l]=='E')s3++;
            if(a[l]=='R')s4++;
            l++;
        }
        else {
            r++;
            if(a[r]=='Q')s1--;
            if(a[r]=='W')s2--;
            if(a[r]=='E')s3--;
            if(a[r]=='R')s4--;
        }
    }
    cout<<ans<<endl;
    return 0;
}