LeetCode 2516. Take K of Each Character From Left and Right

🔗 https://leetcode.com/problems/take-k-of-each-character-from-left-and-right

题目

• 给定一个字符串仅包含 a、b、c，字符串仅可以从头和尾依次取
• 给定一个数字 k，要求 a、b、c 出现的频次都至少为 k，求取出来的字符个数最少值
• 若无法满足条件，返回 -1

思路

• 先判断所有的字符串是否满足 a、b、c 频次大于等于 k，若不满足返回 -1
• two pointer
• 假设从头取 i，那么为了满足条件，从尾部至少取 n-j 个
• 从 0 开始依次遍历 i，从尾部取的长度也依次减少，记录这过程中的最小值

代码

class Solution {
public:
    int takeCharacters(string s, int k) {
        if (k == 0) return 0;
        vector<int> count = {0, 0, 0};
        int n = s.size();
        int j = -1;
        for (int i = n-1; i >= 0; i--) {
            count[s[i] - 'a']++;
            if (j < 0 && count[0] >=k && count[1] >=k && count[2] >=k) {
                j = i;
                break;
            }
        }
        if (j < 0) return -1;
        int ans = n - j ;
        // iterator
        for (int i = 0; i < n; i++) {
            count[s[i]- 'a']++;
            while ( j < n && (count[s[j]- 'a'] -1) >= k) {
                count[s[j]- 'a']--;
                j++;
            }
            ans = min(ans, i + 1 + n - j);
        }

        return ans;
    }
};

原文地址：https://blog.csdn.net/weixin_42383726/article/details/143915816

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