2516.每种字符至少取K个

链接：2516.每种字符至少取K个
难度：Medium
标签：哈希表、字符串、滑动窗口
简介：你必须取走每种字符 至少 k 个，返回需要的 最少 分钟数；如果无法取到，则返回 -1 。

题解 1 - cpp

• 编辑时间：2022-12-25
• 执行用时：24ms
• 内存消耗：14.1MB
• 编程语言：cpp
• 解法介绍：二分答案。

class Solution {
public:
    int takeCharacters(string s, int k) {
        if (k == 0) return 0;
        int l = 0, r = s.size(), m, list[3] = {0};
        for (auto &ch : s) list[ch - 'a']++;
        if (list[0] < k || list[1] < k || list[2] < k) return -1;
        while (l < r) {
            m = (l + r) / 2;
            if (check(s, k, m)) r = m;
            else l = m + 1;
        }
        return l;
    }
    bool check(string &s, int &k, int &m) {
        int list[3] = {0}, l = 0, r = s.size() - m;
        for (int i = s.size() - 1; i >= r; i--) list[s[i] - 'a']++;
        if (checklist(list, k)) return true;
        while (l < m) {
            list[s[l++] - 'a']++;
            list[s[r++] - 'a']--;
            if (checklist(list, k)) return true;
        }
        return false;
    }
    bool checklist(int list[3], int k) {
        return list[0] >= k && list[1] >= k && list[2] >= k;
    }
};

题解 2 - python

• 编辑时间：2024-09-27
• 执行用时：1110ms
• 内存消耗：16.91MB
• 编程语言：python
• 解法介绍：双指针，先假设全部从左侧取值的最大下标，再依次增加右侧取值。

class Solution:
    def takeCharacters(self, s: str, k: int) -> int:
        if k == 0: return 0
        map = defaultdict(int)
        check = lambda : all(v >= k for v in map.values()) and len(map.keys()) == 3
        n = len(s)
        l = 0
        while l < n and not check():
            map[s[l]] += 1
            l += 1
        if not check(): return -1
        res = l
        cur = l
        for r in range(n - 1, -1, -1):
            map[s[r]] += 1
            l -= 1
            map[s[l]] -= 1
            while check() and l > 0:
                res = min(res, cur)
                l -= 1
                map[s[l]] -= 1
                cur -= 1
            if check() and l == 0: res = min(res, cur)
        return res