从Leetcode 每日一题练习继续讨论：
2516. 每种字符至少取 K 个
2516. Take K of Each Character From Left and Right
题解
本题要求返回能取得k个a,b,c字符需要的最少拿取次数，并不能使用贪心，因为选择从左面或者右面拿取字符会影响后面能得到目标结果时拿取的总个数，如左右都是字符a，但左侧第二个字符是b，右侧第二个字符是a，如果只需要每个字符拿1个，拿左侧的a后就可以继续拿取左侧的b，但若拿取右侧的a则想拿取b就要再拿掉左侧的a后才能拿到b。
因此需要考虑左侧的选择会对右侧的选择造成什么影响，要把这种影响全部找出来并记录下来。因此可以找到刚好可以满足题目条件的左侧数组的长度，并将左侧指针指向这个子数组的末尾，在此情况下，当左侧指针向左移动时，左侧数组会不满足题目条件，因此需要右侧数组来补充缺少的字符使得总体满足题目条件，因此右侧指针向左移动直到移动过的部分的右侧数组包含的字符和左侧数组包含的字符和满足题目条件。计算此时左右子数组的长度和，如此反复，直到左侧指针移动到数组开头。
但有可能数组本身就不可能满足题目要求，因此要先判断一下数组中存在的各个字符的个数，如果不满足要求直接返回-1。
代码
class Solution {
public:
int takeCharacters(string s, int k) {
int ca=0,cb=0,cc=0;
int n=s.size();
int ans=n;
for(int i=0;i<n;i++){
if(s[i]=='a') ca++;
if(s[i]=='b') cb++;
if(s[i]=='c') cc++;
}
if(ca<k||cb<k||cc<k) return -1;
int i=n-1,j=n-1;
while(i>=0){
if(s[i]=='a') ca--;
if(s[i]=='b') cb--;
if(s[i]=='c') cc--;
while(ca<k||cb<k||cc<k){
if(s[j]=='a') ca++;
if(s[j]=='b') cb++;
if(s[j]=='c') cc++;
j--;
}
ans=min(ans,i+n-1-j); i--;
}
return ans;
}
};