- 這題同樣是經典的 sliding window,可參考 1658,同樣是頭尾求最短轉換成求最長 window 的題型。
- 接著套不定長 sliding window。
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;
}
};