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;
    }
};

原文地址：https://blog.csdn.net/qq_60624992/article/details/142603631

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！