难度: Medium
给你一个由字符 '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 <= 105s 仅由字母 'a'、'b'、'c' 组成0 <= k <= s.length运行时间: 152 ms
内存: 16.4 MB
class Solution:
def takeCharacters(self, s: str, k: int) -> int:
a = s.count('a')-k
b = s.count('b')-k
c = s.count('c')-k
if a < 0 or b < 0 or c < 0:
return -1
c1 = c2 = c3 = 0
i = 0
ans = 0
for j in range(len(s)):
if s[j] == 'a':
c1 += 1
elif s[j] == 'b':
c2 += 1
else:
c3 += 1
while c1 > a or c2 > b or c3 > c:
if s[i] == 'a':
c1 -= 1
elif s[i] == 'b':
c2 -= 1
else:
c3 -= 1
i += 1
ans = max(ans, j-i+1)
return len(s)-ans
题解采用滑动窗口的方法来找出最短的子数组，使得移除这个子数组后剩余的字符串中每个字符的数量都至少为k。首先计算字符串中每个字符'a'、'b'、'c'的总数减去k，得到a、b、c。如果任何一个字符的总数不足k，则直接返回-1，因为无法满足条件。接着使用一个滑动窗口（通过两个指针i和j定义），遍历字符串，统计窗口中各个字符的数量。如果窗口中某个字符的数量超过了所需的最小数量（比如'a'超过a），则尝试缩小窗口（移动左指针i）以找到最小的满足条件的窗口。最后，计算除去这个窗口外的剩余部分的长度，即为所需的最少分钟数。
时间复杂度: O(n)
空间复杂度: O(1)
# 解决方案类
class Solution:
def takeCharacters(self, s: str, k: int) -> int:
# 计算每个字符超过k的数量
a = s.count('a')-k
b = s.count('b')-k
c = s.count('c')-k
# 如果任何字符数量不足k，直接返回-1
if a < 0 or b < 0 or c < 0:
return -1
# 初始化窗口内的字符计数器
c1 = c2 = c3 = 0
# 初始化滑动窗口的左指针
i = 0
# 初始化答案为0
ans = 0
# 遍历字符串，j为滑动窗口的右指针
for j in range(len(s)):
# 根据字符类型增加计数器
if s[j] == 'a':
c1 += 1
elif s[j] == 'b':
c2 += 1
else:
c3 += 1
# 当窗口内字符数量超过所需时，移动左指针缩小窗口
while c1 > a or c2 > b or c3 > c:
if s[i] == 'a':
c1 -= 1
elif s[i] == 'b':
c2 -= 1
else:
c3 -= 1
i += 1
# 更新答案为最小的窗口大小
ans = max(ans, j-i+1)
# 返回除去窗口外的其他部分的长度
return len(s)-ans
在这个问题中，变量a、b、c代表除去至少k个各字符后，剩余可以用于构成滑动窗口的字符数量。具体地，对于每种字符（'a'、'b'、'c'），我们先计算该字符在整个字符串中的总数，然后减去k。这样，得到的结果就是滑动窗口在理想情况下可以容纳的该字符的最大数量。如果某字符的总数小于k，那么将这个值设为负数，表示不可能构成有效的滑动窗口，因为不能满足每种字符至少有k个的条件。
是的，这个判断可以在遍历字符串之前就确定。在开始滑动窗口算法之前，我们首先计算字符串中每种字符的总数量，并检查每种字符的数量是否至少为k。如果发现任何一个字符的总数少于k，则可以立即返回-1，因为无论如何也无法通过移除部分字符来满足每种字符至少有k个的条件。这个判断是预处理步骤，有助于提前结束算法，避免不必要的计算。
从字符串的两端开始移除字符虽然直观，但可能不会得到最优解。这种方法可能会移除过多的符合条件的字符，特别是当符合条件的字符集中在字符串的中部时。相比之下，滑动窗口方法能够更灵活地调整窗口的大小和位置，寻找到确切的最小的可移除窗口，从而使剩余的字符串部分满足每种字符至少有k个的条件。这种方法更为有效，因为它考虑了字符在整个字符串中的分布，而不仅仅是从两端考虑。
在滑动窗口算法中，目标是找到最小的窗口，使得移除这个窗口后剩余的字符串部分的每种字符数量都至少为k。当窗口内某个字符的数量超过所需的最小数量时，继续增大窗口不会帮助改进结果，反而可能包含更多不需要移除的字符，导致不满足条件或不是最优解。因此，我们尝试缩小窗口，以确保窗口是最小的，并且剩余的每种字符的数量仍满足条件。这样的策略有助于精确控制窗口大小，确保找到最优解。