day-62 每种字符至少取 K 个

思路
滑动窗口：改变思路，从左右两边取字符，是a b c三个字符至少被取k次，那么意味着如果我们知道字符串中a b c的出现个数，那么可以知道取走后剩下子串a b c的个数，问题转化为了求最长子串

解题过程
如果a b c个数分别为x y z，那么取走后剩下子串的a b c的个数分别小于等于x-k,y-k,z-k，所以我们需要找到最长的子串即可（该子串的a b c个数满足分别小于等于x-k,y-k,z-k）

Code

class Solution {public int takeCharacters(String s, int k) {int len=s.length();if(len<3*k) return -1;int a=0;int b=0;int c=0;for(int i=0;i<len;i++){if(s.charAt(i)=='a') a++;else if(s.charAt(i)=='b')b++;else c++;}a=a-k;b=b-k;c=c-k;if(a<0||b<0||c<0) return -1;int ta=0,tb=0,tc=0;int num=-1;for(int left=0,right=0;right<len;right++){if(s.charAt(right)=='a') ta++;else if(s.charAt(right)=='b') tb++;else tc++;if(ta<=a&&tb<=b&&tc<=c){}else{while((ta>a||tb>b||tc>c)&&left<=right){if(s.charAt(left)=='a') ta--;else if(s.charAt(left)=='b') tb--;else tc--;left++;}}num=Math.max(num,right-left+1);}if(num==-1) return -1;else return len-num;}
}作者：菜卷
链接：https://leetcode.cn/problems/take-k-of-each-character-from-left-and-right/solutions/2932655/mei-chong-zi-fu-zhi-shao-qu-k-ge-by-ashi-dpm5/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。