leetcode.每日一题.2516.每种字符至少取 K 个

给你一个由字符 'a'、'b'、'c' 组成的字符串 s 和一个非负整数 k 。每分钟，你可以选择取走 s 最左侧 还是 最右侧 的那个字符。

你必须取走每种字符 至少 k 个，返回需要的 最少 分钟数；如果无法取到，则返回 -1 。

错误代码，不能从两边考虑，思路错误。

class Solution {
public:int takeCharacters(string s, int k) {if(k==0)return 0;int n=s.length();vector<int>idex;int num[4];memset(num,0,sizeof num);for(int i=0;i<n;i++){idex.push_back(++num[int(s[i]-'a')]);}// for(int i=0;i<n;i++)// {//     cout<<idex[i]<<endl;// }for(int i=0;i<3;i++){if(num[i]<k)return -1;}vector<bool>choose(n,0);for(int i=0;i<n;i++){if(idex[i]<=k)choose[i]=1;}int m=0;int maxM=0;for(int i=0;i<n;i++){if(choose[i]==0){m+=1;}else if(choose[i]==1){m=0;}maxM=max(maxM,m);}return n-maxM;}
};

然后看了官方题解的双指针算法，有点思路了。

class Solution {
public:int takeCharacters(string s, int k) {vector<int> cnt(3, 0);int len = s.size();int ans = len;for (int i = 0; i < len; i++) {cnt[s[i] - 'a']++;}if (cnt[0] >= k && cnt[1] >= k && cnt[2] >= k) {ans = min(ans, len);} else {return -1;}int l = 0;for (int r = 0; r < len; r++) {cnt[s[r] - 'a']--;while (l < r && (cnt[0] < k || cnt[1] < k || cnt[2] < k)) {cnt[s[l] - 'a']++;l++;}if (cnt[0] >= k && cnt[1] >= k && cnt[2] >= k) {ans = min(ans, len - (r - l + 1));}}return ans;}
};作者：力扣官方题解
链接：https://leetcode.cn/problems/take-k-of-each-character-from-left-and-right/solutions/2928177/mei-chong-zi-fu-zhi-shao-qu-k-ge-by-leet-10ct/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

首次AC代码

class Solution {
public:int takeCharacters(string s, int k) {if(k==0)return 0;int n=s.length();int num[4];memset(num,0,sizeof num);for(int i=0;i<n;i++){++num[int(s[i]-'a')];}for(int i=0;i<3;i++){if(num[i]<k)return -1;}int l=-1;int maxL=0;for(int r=0;r<n;r++){num[s[r]-'a']-=1;while(l<r&&(num[0]<k||num[1]<k||num[2]<k)){l+=1;num[s[l]-'a']+=1;}maxL=max(maxL,r-l);}return n-maxL;}
};

今日完结撒花~