2024.考试的最大困扰度

链接：2024.考试的最大困扰度
难度：Medium
标签：字符串、二分查找、前缀和、滑动窗口
简介：请你返回在不超过 k 次操作的情况下，最大 连续 'T' 或者 'F' 的数目。

题解 1 - python

• 编辑时间：2024-09-02
• 执行用时：204ms
• 内存消耗：16.68MB
• 编程语言：python
• 解法介绍：滑动窗口。

class Solution:
    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:
        n = len(answerKey)
        def run(ch: str, k: int) -> int:
            left = 0
            right = 0
            while right < n and (k or answerKey[right] == ch):
                if answerKey[right] != ch: k -= 1
                right += 1
            res = right - left
            while right < n:
                if answerKey[right] == ch:
                    res = max(res, right + 1 - left)
                else:
                    while answerKey[left] == ch: left += 1
                    left += 1
                    res = max(res, right - left)
                right += 1
            return res
        return max(run('T', k), run('F', k))

题解 2 - cpp

• 编辑时间：2022-03-29
• 执行用时：24ms
• 内存消耗：11.7MB
• 编程语言：cpp
• 解法介绍：双指针维护中间 k。

class Solution {
   public:
    int maxConsecutiveAnswers(string answerKey, int k) {
        return max(check('T', answerKey, k), check('F', answerKey, k));
    }
    int check(char ch, string str, int k) {
        int n = str.size(), l = 0, r = 0, ans = 0;
        do {
            while (r < n && k > 0) {
                while (r < n && str[r] == ch) r++;
                k--;
                if (r < n) r++;
                while (r < n && str[r] == ch) r++;
            }
            ans = max(ans, r - l);
            while (l < n && k <= 0) {
                if (str[l] != ch) k++;
                l++;
            }
        } while (r < n);
        return ans;
    }
};