2024. 考试的最大困扰度

题目链接：https://leetcode.cn/problems/maximize-the-confusion-of-an-exam/

代码

/**
 * 2024. 考试的最大困扰度
 * https://leetcode.cn/problems/maximize-the-confusion-of-an-exam/
 */

function maxConsecutiveAnswers(answerKey: string, k: number): number {
    let left = 0;
    let res = 0;
    let cnt = 0;
    for (let i = 0; i < answerKey.length; i++) {
        if (answerKey[i] === 'T') {
            cnt++;
        }
        // 窗口合法条件 = 少数派 ≤ k
        while (Math.min(cnt, i - left + 1 - cnt) > k) {
            if (answerKey[left] === 'T') {
                cnt--;
            }
            left++;
        }
        res = Math.max(res, i - left + 1);
    }
    return res;
}

思路

使用滑动窗口：

• 用 cnt 记录当前窗口内 T 的个数；
• 窗口内 F 的个数 = i - left + 1 - cnt；
• 窗口合法条件：少数派（T 和 F 中较少的那个）的数量 ≤ k，即 Math.min(cnt, i - left + 1 - cnt) ≤ k；
• 当窗口不合法时（少数派 > k），移动左指针缩小窗口，直到窗口合法；
• 每次更新窗口长度的最大值。

时间复杂度 $O(n)$，空间复杂度 $O(1)$，其中 $n$ 为字符串长度。