【Leetcode Daily】2024考试的最大困扰度

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给一个由 T 和 F 组成的字符串和一个整数 K，可以对整个字符串做最多 K 次的反转（T<->F），求反转后最长的连续 T 或 F 串长度。

思路分享

• 如果只有单个 T 或 F 就是极其单纯的不定长滑动窗口（【Leetcode Daily】3090每个字符最多出现两次的最长字符串），但他两个都要。

• 陆爻齐直接想到的是都求一次，也就是下面的原始解法。

• 但显然，肯定有更好的方法，根据灵茶山艾府的解法，其实不满足的条件直接算 T 和 F 的记录都大于 K 就行。

  https://leetcode.cn/problems/maximize-the-confusion-of-an-exam/solutions/1028668/zhi-jie-zhao-ban-1004-de-dai-ma-by-endle-42x3/

代码解答（强烈建议自行解答后再看）

• 陆爻齐的原始解法

class Solution {
public:
    int maxConsecutiveAnswers(string answerKey, int k) {
        int max_true = 0, max_false = 0, left = 0;
        int cur_true = 0, cur_false = 0;
        int n = answerKey.size();
        for (int i = 0; i < n; i++) {
            if (answerKey[i]=='T') {
                cur_true++;
            }
            else {
                cur_false++;
            }

            while(cur_false > k) {
                if (answerKey[left++]=='T') {
                    cur_true--;
                }
                else {
                    cur_false--;
                }
            }

            max_true = max(i-left+1, max_true);
        }
        cur_true = 0, cur_false = 0, left = 0;
        for (int i = 0; i < n; i++) {
            if (answerKey[i]=='T') {
                cur_true++;
            }
            else {
                cur_false++;
            }

            while(cur_true > k) {
                if (answerKey[left++]=='T') {
                    cur_true--;
                }
                else {
                    cur_false--;
                }
            }

            max_false = max(i-left+1, max_false);
        }

        return max(max_true, max_false);
    }
};