考试的最大困扰度

难度: Medium

一位老师正在出一场由 n 道判断题构成的考试，每道题的答案为 true （用 'T' 表示）或者 false （用 'F' 表示）。老师想增加学生对自己做出答案的不确定性，方法是 最大化 有 连续相同 结果的题数。（也就是连续出现 true 或者连续出现 false）。

给你一个字符串 answerKey ，其中 answerKey[i] 是第 i 个问题的正确结果。除此以外，还给你一个整数 k ，表示你能进行以下操作的最多次数：

每次操作中，将问题的正确答案改为 'T' 或者 'F' （也就是将 answerKey[i] 改为 'T' 或者 'F' ）。

请你返回在不超过 k 次操作的情况下，最大连续 'T' 或者 'F' 的数目。

示例 1：

输入：answerKey = "TTFF", k = 2
输出：4
解释：我们可以将两个 'F' 都变为 'T' ，得到 answerKey = "TTTT" 。
总共有四个连续的 'T' 。

示例 2：

输入：answerKey = "TFFT", k = 1
输出：3
解释：我们可以将最前面的 'T' 换成 'F' ，得到 answerKey = "FFFT" 。
或者，我们可以将第二个 'T' 换成 'F' ，得到 answerKey = "TFFF" 。
两种情况下，都有三个连续的 'F' 。

示例 3：

输入：answerKey = "TTFTTFTT", k = 1
输出：5
解释：我们可以将第一个 'F' 换成 'T' ，得到 answerKey = "TTTTTFTT" 。
或者我们可以将第二个 'F' 换成 'T' ，得到 answerKey = "TTFTTTTT" 。
两种情况下，都有五个连续的 'T' 。

提示：

n == answerKey.length
1 <= n <= 5 * 10⁴
answerKey[i] 要么是 'T' ，要么是 'F'
1 <= k <= n

Submission

运行时间: 87 ms

内存: 16.1 MB

class Solution:
    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:
        cntB = cntA = left = 0
        for c in answerKey:
            if c == 'T':
                cntB += 1
            else:
                cntA += 1

            if cntB > k and cntA > k:
                if answerKey[left] == 'T':
                    cntB -= 1
                else:
                    cntA -= 1
                left += 1
        return len(answerKey) - left

Explain

此题解采用的是滑动窗口技术来求解问题。主要目标是找到最长的可以通过至多k次变换得到全T或全F的子串。在滑动窗口中，通过两个计数器cntB和cntA分别统计窗口内T和F的数量。窗口从左向右扩展，每次循环读入一个新的字符，并相应地更新计数器。如果窗口内T的数量超过k且F的数量也超过k，则说明当前窗口内无法通过k次变换变为全T或全F。此时需要移动窗口的左边界left，即缩小窗口，直到窗口内的T或F的数量能够被k次操作覆盖。最终，最大的滑动窗口长度即为所求的最大连续字符数。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:
        cntB = cntA = left = 0  # 初始化计数器和窗口左边界
        for c in answerKey:  # 遍历答案键
            if c == 'T':
                cntB += 1  # 累计T的数量
            else:
                cntA += 1  # 累计F的数量

            if cntB > k and cntA > k:  # 如果T和F的数量都超过k，缩小窗口
                if answerKey[left] == 'T':
                    cntB -= 1  # 窗口左端是T，减少计数
                else:
                    cntA -= 1  # 窗口左端是F，减少计数
                left += 1  # 移动窗口左边界
        return len(answerKey) - left  # 返回最大连续字符数

Explore

滑动窗口技术适用于处理数组或字符串中的连续子区间的问题，特别是当需要优化时间复杂度以达到线性时间处理时。对于本题，目标是找到最长的子串，使得该子串通过至多k次变换可以全部变为'T'或全部变为'F'。使用滑动窗口，我们可以有效地在一次遍历中动态调整窗口大小，以找到满足条件的最长子串。相比之下，动态规划可能需要更复杂的状态表示和转移，而且时间和空间复杂度通常会更高，不如滑动窗口方法直观和高效。

在这个题解中，窗口的大小是动态调整的，而不是固定的。窗口从左向右滑动，每次读入一个新的字符扩展窗口的右边界，同时根据条件调整左边界以保证窗口内最多只需要k次变换即可全部变为'T'或'F'。这种动态调整策略确保能覆盖所有可能的最大窗口，因此不存在因窗口大小固定而无法找到最大解的问题。

当`cntB > k`和`cntA > k`时，意味着窗口内的'T'数量和'F'数量都超过了可以通过k次变换来统一的限制。这说明当前窗口无法通过至多k次变换成为全部'T'或全部'F'。因此，需要缩小窗口以尝试减少一个字符类型的数量，使得剩余的字符数量可以被k次变换覆盖。这是为了找到一个合法的子串，即窗口内的字符可以通过至多k次变换全部统一。

在这种滑动窗口策略中，右边界总是在每次迭代中向右移动，以尝试包含更多的字符来找到可能的最长有效子串。当发现当前窗口不再符合条件时（即`cntB > k`和`cntA > k`），移动左边界是为了尝试减小窗口内部的字符计数，使窗口再次符合条件。右边界已经尽可能地扩展了，再移动右边界只会减少窗口大小，无助于寻找更长的有效子串。因此，调整左边界是缩小窗口的合理选择。