Question

2024. 考试的最大困扰度

English Version

题目描述

一位老师正在出一场由 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 = "_FFF_T" 。
或者，我们可以将第二个 'T' 换成 'F' ，得到 answerKey = "T_FFF_" 。
两种情况下，都有三个连续的 'F' 。

示例 3：

输入：answerKey = "TTFTTFTT", k = 1
输出：5
解释：我们可以将第一个 'F' 换成 'T' ，得到 answerKey = "_TTTTT_FTT" 。
或者我们可以将第二个 'F' 换成 'T' ，得到 answerKey = "TTF_TTTTT_" 。
两种情况下，都有五个连续的 'T' 。

 

提示：

• n == answerKey.length
• 1 <= n <= 5 * 104
• answerKey[i] 要么是 'T' ，要么是 'F'
• 1 <= k <= n

解法

方法一：滑动窗口

思路同 1004. 最大连续 1 的个数 III

维护一个单调变长的窗口。这种窗口经常出现在寻求“最大窗口”的问题中：因为要求的是“最大”，所以我们没有必要缩短窗口，于是代码就少了缩短窗口的部分；从另一个角度讲，本题里的 K 是资源数，一旦透支，窗口就不能再增长了。

• l 是窗口左端点，负责移动起始位置
• r 是窗口右端点，负责扩展窗口
• k 是资源数，每次要替换，k 减 1，同时 r 向右移动
• r++ 每次都会执行，l++ 只有资源 k < 0 时才触发，因此 r - l 的值只会单调递增（或保持不变）
• 移动左端点时，如果可以释放一个资源，k 加 1

class Solution:
  def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:
    def get(c, k):
      l = r = -1
      while r < len(answerKey) - 1:
        r += 1
        if answerKey[r] == c:
          k -= 1
        if k < 0:
          l += 1
          if answerKey[l] == c:
            k += 1
      return r - l

    return max(get('T', k), get('F', k))

class Solution {
  public int maxConsecutiveAnswers(String answerKey, int k) {
    return Math.max(get('T', k, answerKey), get('F', k, answerKey));
  }

  public int get(char c, int k, String answerKey) {
    int l = 0, r = 0;
    while (r < answerKey.length()) {
      if (answerKey.charAt(r++) == c) {
        --k;
      }
      if (k < 0 && answerKey.charAt(l++) == c) {
        ++k;
      }
    }
    return r - l;
  }
}

class Solution {
public:
  int maxConsecutiveAnswers(string answerKey, int k) {
    return max(get('T', k, answerKey), get('F', k, answerKey));
  }

  int get(char c, int k, string& answerKey) {
    int l = 0, r = 0;
    while (r < answerKey.size()) {
      if (answerKey[r++] == c) --k;
      if (k < 0 && answerKey[l++] == c) ++k;
    }
    return r - l;
  }
};

func maxConsecutiveAnswers(answerKey string, k int) int {
  get := func(c byte, k int) int {
    l, r := -1, -1
    for r < len(answerKey)-1 {
      r++
      if answerKey[r] == c {
        k--
      }
      if k < 0 {
        l++
        if answerKey[l] == c {
          k++
        }
      }
    }
    return r - l
  }
  return max(get('T', k), get('F', k))
}

function maxConsecutiveAnswers(answerKey: string, k: number): number {
  const n = answerKey.length;
  const getMaxCount = (target: 'T' | 'F'): number => {
    let l = 0;
    let u = k;
    for (const c of answerKey) {
      if (c !== target) {
        u--;
      }
      if (u < 0 && answerKey[l++] !== target) {
        u++;
      }
    }
    return n - l;
  };
  return Math.max(getMaxCount('T'), getMaxCount('F'));
}

impl Solution {
  pub fn max_consecutive_answers(answer_key: String, k: i32) -> i32 {
    let bs = answer_key.as_bytes();
    let n = bs.len();
    let get_max_count = |target| {
      let mut l = 0;
      let mut u = k;
      for b in bs.iter() {
        if b != &target {
          u -= 1;
        }
        if u < 0 {
          if bs[l] != target {
            u += 1;
          }
          l += 1;
        }
      }
      n - l
    };
    get_max_count(b'T').max(get_max_count(b'F')) as i32
  }
}