原文链接: https://leetcode-cn.com/problems/maximize-the-confusion-of-an-exam

英文原文

A teacher is writing a test with n true/false questions, with 'T' denoting true and 'F' denoting false. He wants to confuse the students by maximizing the number of consecutive questions with the same answer (multiple trues or multiple falses in a row).

You are given a string answerKey, where answerKey[i] is the original answer to the ith question. In addition, you are given an integer k, the maximum number of times you may perform the following operation:

• Change the answer key for any question to 'T' or 'F' (i.e., set answerKey[i] to 'T' or 'F').

Return the maximum number of consecutive 'T's or 'F's in the answer key after performing the operation at most k times.

 

Example 1:

Input: answerKey = "TTFF", k = 2
Output: 4
Explanation: We can replace both the 'F's with 'T's to make answerKey = "TTTT".
There are four consecutive 'T's.

Example 2:

Input: answerKey = "TFFT", k = 1
Output: 3
Explanation: We can replace the first 'T' with an 'F' to make answerKey = "FFFT".
Alternatively, we can replace the second 'T' with an 'F' to make answerKey = "TFFF".
In both cases, there are three consecutive 'F's.

Example 3:

Input: answerKey = "TTFTTFTT", k = 1
Output: 5
Explanation: We can replace the first 'F' to make answerKey = "TTTTTFTT"
Alternatively, we can replace the second 'F' to make answerKey = "TTFTTTTT". 
In both cases, there are five consecutive 'T's.

 

Constraints:

• n == answerKey.length
• 1 <= n <= 5 * 104
• answerKey[i] is either 'T' or 'F'
• 1 <= k <= n

中文题目

一位老师正在出一场由 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

通过代码

高赞题解

左右指针确定一个窗口，计算该窗口内T和F的数量，当其中一个小于k的时候，我们可以将那个字母全部改为另一个，从而使窗口中的所有字母相同，因此此时的窗口大小即为一个备选答案，遍历整个字符串得到最大值，就是我们要找的答案。
1）右指针滑动，计算窗口内T和F的数量
2）如果T和F的数量均大于k，即无法通过修改其中一个字母来使窗口内所有字母相同，需要移动左指针
3）左指针移动完毕，此时窗口大小可以作为答案，和当前的最大值比较并更新

class Solution {
    public int maxConsecutiveAnswers(String answerKey, int k) {
        int n = answerKey.length();
        char[] c = answerKey.toCharArray();
        int left = 0, right = 0;
        int numT = 0, numF = 0;
        int ans = 0;
        while(right < n){
            if(c[right] == 'T')
                numT++;
            else
                numF++;
            while(numT > k && numF > k){
                if(c[left] == 'T')
                    numT--;
                else
                    numF--;
                left++;
            }
            ans = Math.max(ans, right - left + 1);
            right++;
        }
        return ans;
    }
}

第一次写题解，有没说清的地方可以问我~

统计信息

通过次数	提交次数	AC比率
2616	5360	48.8%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言