LC2024. 考试的最大困扰度

题目描述

一位老师正在出一场由 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(4) answerKey[i] 要么是 'T' ，要么是 'F' 1 <= k <= n

题目解析

题目在说什么

想象一下，你正在参加一场考试，题目全是判断题（答案只能是 T 或 F）。老师想让你猜不透正确答案，所以他故意把一些答案改来改去，让连续相同答案的题目数量变得尽可能多。

现在你手里有一个字符串 answerKey，比如 "TTFF"，它代表每道题的正确结果。你还有一个“修改次数” k，比如 2，意思是你最多可以改 2 道题的答案（把 T 改成 F，或者把 F 改成 T）。

你的目标：通过最多 k 次修改，让字符串中连续相同字符（全是 T 或全是 F）的长度变得尽可能大。然后输出这个最大长度。

比如 "TTFF" 且 k=2，你可以把两个 F 都改成 T，得到 "TTTT"，连续 T 的长度是 4，所以答案是 4。

思路是怎么来的

这个问题其实可以换个角度想：我们要找一个最长的连续子串，这个子串里出现次数较少的那个字符，它的数量不能超过 k。为什么？因为如果较少的字符数量 ≤ k，我们就可以把它们全部改成另一种字符，让整个子串变成全 T 或全 F。这样，这个子串的长度就是我们要的“连续相同结果”的长度。

比如 "TFFT" 且 k=1，我们想找最长子串。假设子串是 "TFF"（前三个字符），里面 T 出现 1 次，F 出现 2 次，较少的字符是 T（1 次），而 1 ≤ k，所以这个子串合法，长度 3。实际上我们确实可以把那个 T 改成 F，得到 "FFF"。

所以问题变成了：在字符串中找一个最长的子串，使得子串内出现次数较少的那个字符的数量 ≤ k。

怎么找？用“滑动窗口”法。想象你有一个可以伸缩的窗口（左右两个指针），窗口从左向右滑动。你不断把右边的字符加进来，同时检查窗口是否合法（即较少的字符数 ≤ k）。如果不合法，你就从左边移出字符，直到窗口重新合法。每次合法时，记录窗口的长度，取最大值。

这就像你在一个长条上找一段最长的区域，区域里“少数派”不能太多。你用一个可以伸缩的框子去框，框子大了就检查，如果少数派太多，就把框子左边缩一缩，直到少数派数量达标。

代码逐步拆解

我们来看参考代码（Java），一行一行解释。

public int maxConsecutiveAnswers(String answerKey, int k) {
    int num_T = 0, num_F = 0;  // 记录当前窗口内 T 和 F 的个数
    int ans = 0, left = 0;     // ans 是答案，left 是窗口左边界

    for (int right = 0; right < answerKey.length(); right++) {
        char ch = answerKey.charAt(right);  // 当前右指针指向的字符

        // A1: 根据当前字符，增加对应的计数
        if (ch == 'T') {
            num_T++;
        } else {
            num_F++;
        }

        // A2: 如果窗口不合法（较少的字符数 > k），就收缩左边界
        while (Math.min(num_T, num_F) > k) {
            // 左指针指向的字符要被移出窗口
            if (answerKey.charAt(left) == 'T') {
                num_T--;
            } else {
                num_F--;
            }
            left++;  // 左指针右移，窗口缩小
        }

        // A3: 此时窗口合法，更新答案
        ans = Math.max(ans, right - left + 1);
    }