🔗 🟡 2024. Maximize the Confusion of an Exam 1643

tags: `Biweekly Contest 62` `字串(String)` `滑動窗口(Sliding Window)` `前綴和(Prefix Sum)` `二分搜尋(Binary Search)`

題意

一名老師正在編寫一份由 $n$ 個是非題組成的考卷，每個題目的答案為 'T' 或 'F'，老師想通過最大化連續相同答案的題目數量（連續多個正確或連續多個錯誤）來迷惑學生。

給定一個字串 $answerKey$ ，其中 $answerKey[i]$ 是第 $i$ 個問題的正確答案。另給定一個整數 $k$ ，表示最多可以執行以下操作的次數：

在每次操作中，可以將任何問題的正確答案改為 'T' 或 'F'（也就是將 $answerKey[i]$ 改為 'T' 或 'F'）。

請返回在執行最多 $k$ 次操作後，答案中連續 'T' 或 'F' 的最大數量。

思路：滑動窗口(Sliding Window)

首先先考慮 'T' 的情況，對於 'T' 以外的字元 (即 'F') ，可以透過修改來將其改為 'T' ，而修改次數最多為 $k$ 次。因此可以將問題轉換為：找到一個最長的子字串，且子字串中 'F' 的個數不超過 $k$ 個。對於 'F' 的情況同理，兩者的結果取最大值即可。

而上述目標可以透過滑動窗口(Sliding Window) 來解決，以連續 'T' 的情況為例：

使用兩個指標 $left$ 和 $right$ 來維護一個窗口，分別代表當前窗口左邊界和右邊界。
使用 $cnt$ 來記錄當前窗口內有多少個 'T' 以外的字元 (即 'F') 。
使用 $res$ 來記錄在所有滿足條件的窗口中，最大的窗口大小。

透過移動窗口的右端點 $right$ 不斷將新的元素加入窗口，並檢查是否符合要求（即：窗口中與目標字元不同的數量是否小於或等於 $k$ ）。

如果 $cnt > k$ ，則透過移動窗口的左邊界 $left$ 來縮小窗口，直到再次滿足條件。
當滿足條件時，當前窗口的大小 $right - left + 1$ ，更新答案。

由於我們需要檢查兩個情況，因此可以使用一個 helper 函數來實現。最後取 max(helper('T'), helper('F')) 即可。

複雜度分析

時間複雜度： $\mathcal{O}(n)$ ，其中 $n$ 是字串的長度。
空間複雜度： $\mathcal{O}(1)$ 。

class Solution:
    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:
        n = len(answerKey)
        def helper(ch: str):
            cnt = 0 # 窗口中 ch 的個數
            left = 0 # 左端點
            res = 0 # 窗口的最大長度
            for right in range(n): # 枚舉右端點，入窗口
                if answerKey[right] == ch:
                    cnt += 1
                while cnt > k: # 不滿足條件，開始縮小窗口
                    if answerKey[left] == ch:
                        cnt -= 1
                    left += 1
                res = max(res, right - left + 1) # 更新答案
            return res
        return max(helper('T'), helper('F'))

class Solution {
public:
    int maxConsecutiveAnswers(string answerKey, int k) {
        int n = answerKey.size();
        function<int(char)> helper = [&](char ch) {
            int left = 0, cnt = 0, res = 0;
            for (int right = 0; right < n; right++) {
                if (answerKey[right] == ch) cnt++;
                while (cnt > k) {
                    if (answerKey[left] == ch) cnt--;
                    left++;
                }
                res = max(res, right - left + 1);
            }
            return res;
        };
        return max(helper('T'), helper('F'));
    }
};