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

class Solution {
public:
    int takeCharacters(string s, int k) {
        // 先檢驗題目本身有沒有可能符合，因為 s 至少要 3 * k 才可能有解
        int need = k * 3;
        int n = s.size();
        if (n < need) return -1;
        int cnt[3];
        memset(cnt, 0, sizeof(cnt));
        for (const auto& c : s) {
            cnt[c-'a']++;
        }
        // 檢查各字元是否至少有 k 個
        for (int i = 0; i < 3; i++) {
            if (cnt[i] < k) return -1;
            cnt[i] -= k;
        }
        // 如果都符合，字串長度又剛好等於 need，那必定是整個 string 都需要
        if (n == need) return n;

        // 剩下的就是經典的 sliding window，滑起來就是了
        int left = 0, right = 0, res = 0;
        int curr[3];
        memset(curr, 0, sizeof(curr));
        while (right < n) {
            char c = s[right++];
            curr[c-'a']++;
            while (curr[c-'a'] > cnt[c-'a']) {
                curr[s[left++]-'a']--;
            }
            res = max(res, right-left);
        }
        // 注意要還原
        return n - res;
    }
};