2516.每种字符至少取 K 个

题目

给你一个由字符 'a'、'b'、'c' 组成的字符串 s 和一个非负整数 k 。每分钟，你可以选择取走 s 最左侧 还是 最右侧 的那个字符。

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

示例 1：

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

示例 2：

1
2
3

输入：s = "a", k = 1
输出：-1
解释：无法取到一个字符 'b' 或者 'c'，所以返回 -1 。

提示：

1 <= s.length <= 105
s 仅由字母 'a'、'b'、'c' 组成
0 <= k <= s.length

题解

class Solution {
    public int takeCharacters(String s, int k) {
        int[] remains = new int[3]; // 每个字符取k个后，应剩余的个数
        int[] counts = new int[3]; // 该字符串中每个字符的个数
        int n=s.length();
        for(int i=0;i<n;i++){
            char c = s.charAt(i);
            counts[c-'a']++;
        }
        // 不满足取的条件
        for(int i=0;i<3;i++){
            remains[i]= counts[i]-k;
            if(remains[i]<0){
                return -1;
            }
        }
        int ans=0;
        for(int left=0,right=0;right<n;right++){
            char c=s.charAt(right); // 该字符在剩余字符串中
            remains[c-'a']--;
            while(remains[c-'a']<0){
                char p = s.charAt(left);
                remains[p-'a']++;
                left++;
            }
            ans = Math.max(ans,right-left+1);
        }
        return n-ans;
    }
}