LeetCode 题解工作台
考试的最大困扰度
一位老师正在出一场由 n 道判断题构成的考试，每道题的答案为 true （用 'T' 表示）或者 false （用 'F' 表示）。老师想增加学生对自己做出答案的不确定性，方法是 最大化 有 连续相同 结果的题数。（也就是连续出现 true 或者连续出现 false）。 给你一个字符串 answer…
4
题型
6
代码语言
3
相关题
当前训练重点
中等 · 二分·搜索·答案·空间
答案摘要
我们设计一个函数 ，表示最多替换 个字符 的情况下，最长的连续字符的长度，其中 可以是 'T' 或 'F'。答案就是 $\max(\textit{f}('T'), \textit{f}('F'))$。 我们遍历字符串 ，用一个变量 记录当前窗口内字符 的个数，当 $\textit{cnt} > k$ 时，我们将窗口的左指针右移一位。遍历结束后，窗口的长度即为最大连续字符的长度。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·搜索·答案·空间 题型思路
题目描述
一位老师正在出一场由 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.length1 <= n <= 5 * 104answerKey[i]要么是'T'，要么是'F'1 <= k <= n
解题思路
方法一：滑动窗口
我们设计一个函数 ，表示最多替换 个字符 的情况下，最长的连续字符的长度，其中 可以是 'T' 或 'F'。答案就是 。
我们遍历字符串 ，用一个变量 记录当前窗口内字符 的个数，当 时，我们将窗口的左指针右移一位。遍历结束后，窗口的长度即为最大连续字符的长度。
时间复杂度 ，其中 是字符串的长度。空间复杂度 。
相似题目：
class Solution:
def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:
def f(c: str) -> int:
cnt = l = 0
for ch in answerKey:
cnt += ch == c
if cnt > k:
cnt -= answerKey[l] == c
l += 1
return len(answerKey) - l
return max(f("T"), f("F"))
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n log n) due to binary search over possible lengths and O(n) sliding window checks for each length. Space complexity is O(1) for counters and window indices, ignoring input storage. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for a solution combining binary search with a sliding window over the answerKey.
- question_mark
Consider how previous window calculations can help determine feasibility of the current candidate length.
- question_mark
Check handling of edge cases where k is large enough to flip all answers or very small with alternating patterns.
常见陷阱
外企场景- error
Failing to check both 'T' and 'F' as the target character when maximizing consecutive length.
- error
Not shrinking the sliding window correctly when flips exceed k, leading to incorrect results.
- error
Assuming consecutive maximum always starts at index 0, ignoring overlapping windows later.
进阶变体
外企场景- arrow_right_alt
Maximizing consecutive answers with multiple choice options instead of just T/F.
- arrow_right_alt
Finding the minimum flips needed to achieve a given consecutive length.
- arrow_right_alt
Applying the same binary search and sliding window approach to a circular exam string.