Medium

题目描述

老师正在准备一场有 n 道判断题的考试，其中 ‘T’ 表示正确，‘F’ 表示错误。老师想通过最大化连续相同答案的题目数量来困惑学生（连续的多个 T 或连续的多个 F）。

给你一个字符串 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⁴
  • answerKey[i] 为 ‘T’ 或 ‘F’
  • 1 <= k <= n

解题思路

这是一道经典的滑动窗口问题。核心思想是分别考虑将字符串变成全 ‘T’ 和全 ‘F’ 两种情况，取其中的最大值。

解题思路：

  1. 问题转化：原问题可以转化为在最多改变 k 个字符的前提下，能够得到的最长连续相同字符子串的长度。

  2. 滑动窗口策略：

    • 分别考虑将窗口内所有字符变为 ‘T’ 和变为 ‘F’ 两种情况
    • 对于每种情况，使用滑动窗口维护一个区间，使得区间内需要修改的字符数不超过 k

  3. 具体实现：

    • 使用双指针 left 和 right 维护滑动窗口
    • count 记录当前窗口内需要修改的字符数量
    • 当 count 超过 k 时，缩小左边界直到 count <= k
    • 不断更新最大窗口长度

  4. 优化：可以将两次滑动窗口合并为一个函数，分别以 ‘T’ 和 ‘F’ 为目标字符调用。

时间复杂度为 O(n)，空间复杂度为 O(1)，是最优解法。

代码实现

class Solution {
public:
    int maxConsecutiveAnswers(string answerKey, int k) {
        return max(helper(answerKey, k, 'T'), helper(answerKey, k, 'F'));
    }
    
private:
    int helper(string& answerKey, int k, char target) {
        int left = 0, right = 0, count = 0, maxLen = 0;
        
        while (right < answerKey.length()) {
            if (answerKey[right] != target) {
                count++;
            }
            
            while (count > k) {
                if (answerKey[left] != target) {
                    count--;
                }
                left++;
            }
            
            maxLen = max(maxLen, right - left + 1);
            right++;
        }
        
        return maxLen;
    }
};

class Solution:
    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:
        def helper(target):
            left = count = 0
            max_len = 0
            
            for right in range(len(answerKey)):
                if answerKey[right] != target:
                    count += 1
                
                while count > k:
                    if answerKey[left] != target:
                        count -= 1
                    left += 1
                
                max_len = max(max_len, right - left + 1)
            
            return max_len
        
        return max(helper('T'), helper('F'))

public class Solution {
    public int MaxConsecutiveAnswers(string answerKey, int k) {
        return Math.Max(Helper(answerKey, k, 'T'), Helper(answerKey, k, 'F'));
    }
    
    private int Helper(string answerKey, int k, char target) {
        int left = 0, count = 0, maxLen = 0;
        
        for (int right = 0; right < answerKey.Length; right++) {
            if (answerKey[right] != target) {
                count++;
            }
            
            while (count > k) {
                if (answerKey[left] != target) {
                    count--;
                }
                left++;
            }
            
            maxLen = Math.Max(maxLen, right - left + 1);
        }
        
        return maxLen;
    }
}

var maxConsecutiveAnswers = function(answerKey, k) {
    const helper = (target) => {
        let left = 0, count = 0, maxLen = 0;
        
        for (let right = 0; right < answerKey.length; right++) {
            if (answerKey[right] !== target) {
                count++;
            }
            
            while (count > k) {
                if (answerKey[left] !== target) {
                    count--;
                }
                left++;
            }
            
            maxLen = Math.max(maxLen, right - left + 1);
        }
        
        return maxLen;
    };
    
    return Math.max(helper('T'), helper('F'));
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)每个字符最多被访问两次（右指针和左指针各一次）
空间复杂度O(1)只使用常数额外空间

相关题目