逆向滑动窗口

每种字符至少取 K 个

给你一个由字符 'a'、'b'、'c' 组成的字符串 s 和一个非负整数 k 。

你可以选择取走 s 最左侧 还是 最右侧 的那个字符。

你必须取走每种字符 至少 k 个，返回需要取走的最少字符串数量；如果无法取到，则返回 -1 。

输入：s = "aabaaaacaabc", k = 2
输出：8
解释：
从 s 的左侧取三个字符，现在共取到两个字符 'a' 、一个字符 'b' 。
从 s 的右侧取五个字符，现在共取到四个字符 'a' 、两个字符 'b' 和两个字符 'c' 。
共需要 3 + 5 = 8 个

其实就是一个逆向滑动窗口，之前的滑动窗口都是左右指针找到一个符合条件的区间

而这题可以找到最长的不符合题意的区间，然后用总长度减去这个区间长度即可

class Solution {
    //逆向滑动窗口
    public int takeCharacters(String s, int k) {
        int maxLen = 0;
        int n = s.length();
        int[] count = new int[3];
        char[] arr = s.toCharArray();
        for(char c:arr){
            count[c-'a']++;
        }
        //使用remain来记录最多可以剔除的字母个数
        int[] remain = new int[3];
        for(int i=0;i<3;i++){
            remain[i]=count[i]-k;
            //如果小于零，证明整个字符串都无法满足条件，直接返回-1
            if(remain[i]<0) return -1;
        }
        //滑动窗口代码逻辑，找到最多可以减去的，不影响k个数的最长字符串
        int[] window = new int[3];
        int left=0,right=0;
        while(right<n){
            //更新窗口
            char c = arr[right];
            window[c-'a']++;
            //窗口收缩条件：窗口内的字母个数超过了最多可以剔除的个数，收缩到不影响k个数
            while(window[c-'a']>remain[c-'a']){
                char temp = arr[left];
                window[temp-'a']--;
                left++;
            }
            maxLen = Math.max(maxLen,right-left+1);
            right++;
        }
        return n-maxLen;
    }
}