class Solution {
    public int balancedString(String s) {
        //涉及到了子串问题，可以考虑使用滑动窗口
        //当把窗口内包含的串作为被替换子串时，我们就需要保证窗口外的每个字符都是
        //小于或者等于s长度的1/4.
        //枚举所有的允许被替换的子串，并取出其中最短的长度作为返回值即可
        int[] counts = new int[26];
        int target = s.length()/4;
        for(int i=0;i<s.length();i++){
            counts[s.charAt(i)-'A']++;
        }
        //使用滑动窗口,左闭右开区间，所以区间长度为r-l
        int res = s.length();//最长替换不会超过整个字符串长度
        int l=0;
        int r=0;
        while(r<s.length()){
            if(!isMatch(counts,target)){
                //每次循环想窗口内扩充一个字符
                //期望寻找一个可行解
                //System.out.println("扩充窗口为：["+l+","+r+")");
                counts[s.charAt(r)-'A']--;
                r++;
            }
            //符合条件，则尝试增大l，以优化可被替换子串的长度
            if(isMatch(counts,target)){
                if(r==l){
                    //System.out.println("不用替换");
                    return 0;//不用替换，那就直接返回0即可
                }else{
                    //不能以0返回，是一定能保证有超多出现的字母，所以窗口中至少有一个元素
                    //说明窗口内是有元素的，左端点的元素一定是有的:l<r
                    while(isMatch(counts,target)){
                        //System.out.println("找到一个符合条件的窗口：["+l+","+r+")");
                        res = Math.min(res,r-l);
                        counts[s.charAt(l)-'A']++;//放回窗口外
                        l++;
                    }
                }
            }
        }
        return res;
    }
    private boolean isMatch(int[] counts,int target){
        return counts['Q'-'A']<=target&&
                counts['W'-'A']<=target&&
                counts['E'-'A']<=target&&
                counts['R'-'A']<=target;
    }
}