目标
一位老师正在出一场由 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
思路
有一个字符串 answerKey 由 T 或 F 组成, 允许我们执行 k 次操作，每次操作可以将字符串中的 T 改为 F 或者 F 改为 T。问 T 或 F 可能的最大连续个数。
这道题没有做出来，想着使用动态规划去做，但是没有找到合适的状态定义。比如 dp[i][j][k] 表示 [0,i] 以 T 或 F 结尾剩余操作次数 k 时的最大连续个数。2 x 10^8 的存储空间肯定不行。
题解说是滑动窗口、或者 前缀和 + 二分查找，也有使用动态规划的。
这道题的难点在于想明白这 k 次操作必须统一，要么全部从 T 改为 F，要么全部从 F 改为 T，才能使连续个数最大。因为如果 T 的连续个数最多，并且存在将 T 改为 F 的操作，那么我们总可以撤回该操作，并将一个 F 改为 T（如果存在的话，如果不存在说明全是T，撤销操作也会加一） 使得连续个数至少加一。
网友题解中的动态规划是这样定义的 dp[i] 表示 [0,i] 中以 answerKey[i] 结尾的连续后缀个数。这里的前提就是遇到不连续的统一从 T 改为 F 或者 从 F 改为 T 使之连续，如果超过了可操作的次数，需要撤回最早的操作，使得当前后缀连续。后缀连续个数可以用当前下标减去最早进行操作的下标计算得到（使用链表保存操作的下标，获取链表head记录的下标后将其删，再将当前下标加入链表末尾）。在计算dp过程中记录其最大值即为最大连续个数。如果对这个动态规划进行存储优化，那就是滑动窗口。
寻找一个窗口，使得窗口内的 T 或者 F 个数小于等于 k，并且使 F 或者 T 的个数最大。滑动窗口的套路一般是枚举右边界，如果条件不满足，更新左边界直到条件满足。
二分的做法本质也是滑动窗口，枚举左边界，二分查找能够到达的最远右边界。
代码
/**
* @date 2024-09-02 16:55
*/
public class MaxConsecutiveAnswers2024 {
/**
* 前缀和 + 二分查找
* 其实本质也是滑动窗口，枚举左边界，二分查找最远的右边界
* O(nlogn) 62ms
*/
public int maxConsecutiveAnswers_v1(String answerKey, int k) {
int n = answerKey.length();
int[] prefix = new int[n + 1];
for (int i = 1; i <= n; i++) {
if (answerKey.charAt(i - 1) == 'T') {
prefix[i] = prefix[i - 1] + 1;
} else {
prefix[i] = prefix[i - 1];
}
}
int res = 0;
for (int i = 1; i <= n; i++) {
int l = i, r = n;
int mid = l + (r - l) / 2;
while (l <= r) {
int num = mid - i + 1;
int cnt = prefix[mid] - prefix[i - 1];
if (num - cnt <= k || cnt <= k) {
l = mid + 1;
} else {
r = mid - 1;
}
mid = l + (r - l) / 2;
}
res = Math.max(res, r - i + 1);
}
return res;
}
/**
* 滑动窗口 O(n)
* 21ms
*/
public int maxConsecutiveAnswers(String answerKey, int k) {
return Math.max(process(answerKey, k, 'T'), process(answerKey, k, 'F'));
}
public int process(String answerKey, int k, char turnTo) {
int n = answerKey.length();
int res = 0;
List<Integer> optsIndex = new LinkedList<>();
int cnt = 0;
for (int i = 0; i < n; i++) {
if (answerKey.charAt(i) != turnTo) {
if (k > 0) {
k--;
optsIndex.add(i);
cnt++;
} else {
cnt = i - optsIndex.remove(0);
optsIndex.add(i);
}
} else {
cnt++;
}
res = Math.max(res, cnt);
}
return res;
}
}
性能
