考试的最大困扰度

说在前面

🎈不知道大家对于算法的学习是一个怎样的心态呢？为了面试还是因为兴趣？不管是出于什么原因，算法学习需要持续保持。

1、题目描述

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

2、思路分析

题目要求我们在只修改最多k个字母的前提下，计算修改后可获得连续字符串的最大长度。

如上图所示，黑色箭头代表左端点，红色箭头代表当前遍历位置，我们可以看到红色箭头1对应的黑色箭头1移到了第一个F的后面，具体移动逻辑如下：
我们可以使用left来记录当前连续区间的左端点，step记录当前需要进行修改的字母数，当step等于k，即修改次数已经达到最大，只能将左端点往右移，移到第一个需要修改的字母后面，也就是将这次修改机会转移给当前遍历到的这个字母使用，这时区间才能满足要求，我们只需要不断更新区间长度最大值就可以得到答案了。
这是一个典型的移动窗口思想，可以帮助我们解决很多连续字符串的相关问题。

3、AC代码

/**
 * @param {string} answerKey
 * @param {number} k
 * @return {number}
 */
var maxConsecutiveAnswers = function (answerKey, k) {
  let check = function (ch) {
    let res = 0,
      left = 0,
      step = 0;
    for (let i = 0; i < answerKey.length; i++) {
      if (answerKey[i] !== ch) {
        if (step === k) {
          while (left < i && answerKey[left] === ch) left++;
          left++;
        } else {
          step++;
        }
      }
      res = Math.max(res, i - left + 1);
    }
    return res;
  };
  let res = Math.max(check("T"), check("F"));
  return res;
};

公众号

关注公众号『前端也能这么有趣』，获取更多有趣内容。

说在后面

🎉 这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打羽毛球 🏸 ，平时也喜欢写些东西，既为自己记录 📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解 🙇，写错的地方望指出，定会认真改进 😊，偶尔也会在自己的公众号『前端也能这么有趣』发一些比较有趣的文章，有兴趣的也可以关注下。在此谢谢大家的支持，我们下文再见 🙌。