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：

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

提示：

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

逆向思维，把问题转化为「去掉一个最长子数组，使得剩下的’a’,’b’,’c’个数都>=k」
这样又变成了经典的滑动窗口求满足条件的子数组最大长度问题了

class Solution {
    public int takeCharacters(String s, int k) {
        int n = s.length();      
        //记录'a','b','c'出现次数
        int[] map = new int[3];
        var chars = s.toCharArray();
        for (char cur : chars) {
            map[cur - 'a']++;
        }
        //出现次数都不满足 k
        if (map[0] < k || map[1] < k || map[2] < k) {
            return -1;
        }
        //刚好满足
        if (map[0] == k && map[1] == k && map[2] == k) {
            return n;
        }

        int res = -1, left = 0;
        for (int right = 0; right < n; right++) {
            //右端点右移
            map[chars[right] - 'a']--;
            //如果剩下的字符不满足条件了，左端点右移
            while (map[0] < k || map[1] < k || map[2] < k) {
                map[chars[left] - 'a']++;
                left++;
            }
            //剩下的满足「至少 k 个」
            if (map[0] >= k && map[1] >= k && map[2] >= k) {
                res = Math.max(res, right - left + 1);
            }
        }
        return res == -1 ? -1 : n - res;
    }
}

相似题目：

• 1658. 将 x 减到 0 的最小操作数