考试的最大困扰度-LeetCode

2024. 考试的最大困扰度

🎯 问题描述（来源于LeetCode）

描述：
一位老师正在出一场判断题测试，其中每道题的答案都是 ‘T’ (真) 或 ‘F’ (假)。
给你一个字符串 answerKey，其中 answerKey[i] 是第 i 题的正确答案。
同时给你一个整数 k，表示你最多可以执行 k 次操作。
每次操作你可以将任意一题的答案从 ‘T’ 改为 ‘F’，或者从 ‘F’ 改为 ‘T’。
请你返回在不超过 k 次操作的情况下，最大连续 ‘T’ 或者 ‘F’ 的数目。

说明：

• 这是一个不定长滑动窗口问题。

• 题目要求最大化连续相同字符的长度，这意味着我们需要找到一个子串，其中少数派字符的数量不超过 k（因为我们可以把少数派改成多数派）。

• 策略：分别计算“将 ‘F’ 改为 ‘T’”和“将 ‘T’ 改为 ‘F’”两种情况下的最大长度，取最大值。

• 示例：

• 示例 1：

输入：answerKey = "TTFF", k = 2
输出：4
解释：我们可以将两个 'F' 都变成 'T'，得到 "TTTT"。
或者将两个 'T' 都变成 'F'，得到 "FFFF"。

• 示例 2：

输入：answerKey = "TFFT", k = 1
输出：3
解释：
- 将第一个 'T' 改为 'F'，得到 "FFFT"，连续 'F' 长度为 3。
- 或者将最后一个 'T' 改为 'F'，得到 "TFFF"，连续 'F' 长度为 3。
- 无法得到长度为 4 的连续相同字符。

💻 解题思路

思路1：双向滑动窗口

思路1：代码实现

class Solution:
    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:
        # 第一次遍历：尝试将所有 'F' 变成 'T'
        # 也就是寻找包含最多 k 个 'F' 的最长子串
        T_k = Counter()
        ans_T = 0
        left = 0
        for right, st in enumerate(answerKey):
            T_k[st] += 1
            # 当窗口内 'F' 的数量超过 k 时，收缩左边界
            while T_k["F"] > k:
                T_k[answerKey[left]] -= 1
                left += 1
            ans_T = max(ans_T, right - left + 1)
            
        # 第二次遍历：尝试将所有 'T' 变成 'F'
        # 也就是寻找包含最多 k 个 'T' 的最长子串
        F_k = Counter()
        ans_F = 0
        left = 0
        for right, st in enumerate(answerKey):
            F_k[st] += 1
            # 当窗口内 'T' 的数量超过 k 时，收缩左边界
            while F_k["T"] > k:
                F_k[answerKey[left]] -= 1
                left += 1        
            ans_F = max(ans_F, right - left + 1)
            
        # 返回两种情况的最大值
        return max(ans_F, ans_T)

思路1：📊 性能分析

• 时间复杂度：$O(N)$
  • 其中 $N$ 是字符串 answerKey 的长度。
  • 虽然代码中有两个 for 循环，但它们是顺序执行的，且每个循环内部都是线性的滑动窗口操作。总时间复杂度为 $O(2N) \approx O(N)$。
• 空间复杂度：$O(1)$
  • 哈希表 T_k 和 F_k 最多存储 2 个键值对（‘T’ 和 ‘F’），因此空间复杂度是常数级别。

思考

1. 问题拆解：

   • 题目要求“连续 ‘T’ 或者 ‘F’”，这暗示我们需要分别考虑两种目标情况。
   • 情况 A：目标是全 ‘T’。这意味着窗口内最多允许有 k 个 ‘F’（作为被替换的对象）。
   • 情况 B：目标是全 ‘F’。这意味着窗口内最多允许有 k 个 ‘T’。

2. 滑动窗口逻辑：

   • 在第一次遍历中，T_k["F"] 记录了当前窗口内 ‘F’ 的数量。
   • while T_k["F"] > k: 保证了我们只保留那些可以通过 k 次操作变成全 ‘T’ 的子串。
   • 第二次遍历同理，只是监控对象变成了 ‘T’。

3. 代码结构：

   • 代码重复了两次几乎相同的逻辑，这是解决此类“二选一”最值问题的常用且清晰的方法。
   • 也可以将其封装成一个辅助函数来减少代码重复，但目前的写法直观易懂。

4. 变量命名：

   • T_k 和 F_k 的命名略显简略，实际上它们分别代表“为了变成 T 而统计的计数器”和“为了变成 F 而统计的计数器”。
   • ans_T 和 ans_F 分别代表这两种策略下的最优解。

思路2：单趟滑动窗口（巧妙解法）

描述：
尝试在一次遍历中同时维护 ‘T’ 和 ‘F’ 的计数，并通过一个 while 循环来处理两种情况。

思路2：代码实现

class Solution:
    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:
        ans = left = 0
        cnt = defaultdict(int)
        for right, ch in enumerate(answerKey):
            cnt[ch] += 1
            # ⚠️ 注意：这里的逻辑是 "and"，不是 "or"
            # 只有当 T 和 F 的数量都超过 k 时，才收缩窗口
            while cnt['T'] > k and cnt['F'] > k:
                cnt[answerKey[left]] -= 1
                left += 1
            ans = max(ans, right - left + 1)
        return ans

思路2：📊 性能分析

• 时间复杂度：$O(N)$
  • 其中 $N$ 是字符串 answerKey 的长度。
• 空间复杂度：$O(1)$
  • 哈希表最多存储 2 个键值对（‘T’ 和 ‘F’），因此空间复杂度是常数级别。