2516. 每种字符至少取 K 个（24.9.27）

题目

给定一个由字符 '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 <= 19^5
• s 仅由字母 'a'、'b'、'c'组成
• 0 <= k <= s.length

解题思路

本条题目可以通过逆向思考过程，从左侧或者右侧取字母，转换为不取哪些数，我们很快发现不取的部分则是一个标准的滑动窗口。我们首先统计所有的a、b、c的数量cnt数组，此时的cnt表示为可取的数量，这就意味着cnt>=k，设r和l分别表示窗口的右端点和左端点，当我们将右端的字符加进来（r++）时则意味着这个字符无法被获取了，我们需要将对应的cnt--，当cnt<k时，则不满足题目的条件，对应的将左端给踢出窗口（l++），那么将cnt++ 直到我们最右端的cnt满足条件。窗口设计完后我们重新思考题目，假设我们的窗口长度为len(len=r-l+1),字符串的总大小为Size，那么我们对应的答案为Size-len，要想答案最小，而Size大小不变，那么这就要求len最大，则问题就变成了求解窗口的最大长度。

代码

class Solution {
public:int takeCharacters(string s, int k) {int ans=-1;vector<int> cnt(3);for(int i=0;i<s.size();i++){cnt[s[i]-'a']++;}if(cnt[0]<k||cnt[1]<k||cnt[2]<k) return -1;int l=0;for(int r=0;r<s.length();r++){int index_r=s[r]-'a';//将右端移入窗口，说明不取，从记录中删除cnt[index_r]--;while(cnt[index_r]<k){//小于k，说明int index_l=s[l++]-'a';cnt[index_l]++;}ans=max(ans,r-l+1);}return s.size()-ans;}
};