目标
给你一个由字符 '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 <= 10^5
- s 仅由字母 'a'、'b'、'c' 组成
- 0 <= k <= s.length
思路
有一个仅由 a、b、c 组成的字符串，每一分钟可以选择访问两端（最左侧/最右侧）的未访问字符，求访问 a、b、c 每种字符至少 k 次最少需要多少分钟。
可以将字符串拼接到末尾，问题转化为滑动窗口问题，求使窗口内包含k个 a、b、c 的最小窗口长度。但这里有一个限制，窗口必须包含首尾交界点，就像有一个轴在窗口里面，窗口可以左右延展。
我们可以先向左侧滑动，找到满足条件的最左侧下标，然后枚举左端点向右滑动，直到左边界越过交界点，枚举的过程中延展右边界直到满足条件。
官网题解中使用了逆向思维，先求出字符串中 a、b、c 的个数，窗口在中间滑动，窗口内的 a、b、c 是不选的，使用总数减去窗口内的计数判断是否满足条件。
代码
/**
* @date 2024-09-27 9:12
*/
public class TakeCharacters2516 {
public int takeCharacters(String s, int k) {
if (k == 0) {
return 0;
}
int res = Integer.MAX_VALUE;
int[] cnt = new int[3];
char[] chars = s.toCharArray();
int n = chars.length;
int l = n - 1;
while (l >= 0 && (cnt[0] < k || cnt[1] < k || cnt[2] < k)) {
cnt[chars[l--] - 'a']++;
}
if (cnt[0] < k || cnt[1] < k || cnt[2] < k) {
return -1;
}
l++;
int r = n;
int doubleN = 2 * chars.length;
for (; l <= n; l++) {
while (r < doubleN && (cnt[0] < k || cnt[1] < k || cnt[2] < k)) {
cnt[chars[r++ % n] - 'a']++;
}
res = Math.min(res, r - l);
if (l == n) {
break;
}
cnt[chars[l] - 'a']--;
}
return res;
}
}
性能
