考试的最大困扰度 图解题解

一串 T 和 F 最多翻 k 次，到底在求什么

给一个只由 T 和 F 组成的字符串 answerKey 和次数 k，每次操作能把某个字符改成 T 或 F，最多做 k 次，问改完后最长连续相同字符段能多长。题面 answerKey 为 TTFTTFTT、k 为 1 时答案是 5：把下标 2 的 F 改成 T，前面五个位置连成一片 T。若 k 为 0、串是 TFFT 一个都不能改，最长同字符段只有 2。

枚举每一段子串数翻转，为什么算不动

答案串可能长到 5 万个字符。硬办法是圈定每个连续子串、数出少数派要翻几个，够 k 就拿长度比最大值。这样的子串约 n²/2 个，逐个还要数一遍，逼近 O(n³)；一边挪一边带计数省掉重复也只压到 O(n²)，平方约 25 亿次，跑不完。

少数派不超过 k，一个窗口凭什么够用

任取一段连续区间要整段变成同一个字符，只需把偏少的那派翻过去，多的留着当底色最省。所以这段要花的操作数正是少数派的个数；只要它不超过 k，就能在预算内刷成纯色，长度便是一个候选答案。

偏少的那派可能是 T、也可能是 F，所以「少数派不超过 k」这一条同时管住「最后全 T」和「最后全 F」两种打算，不必分开试。问题于是变成找最长的、少数派不超过 k 的连续区间。滑动窗口（拿左右两个边界圈住一段、右边界往右扩、左边界视情况跟进）正好对口：区间越长越好，一超预算就从左边收。

右边界扩、左边界追，窗口怎么挪

备两个计数，记当前窗口里 T 和 F 各有多少。右边界每往右吞一格就把新字符计进来。若此刻少数派超过 k，这段就翻不动了，从左边界往里踢字符、把被踢那派的计数减一，踢到少数派落回 k 以内；只踢一格往往不够，得用循环踢到合法。每当窗口合法，就用它的长度刷新记录的最大值。要翻的次数始终是 min(cntT, cntF)，不是较多的那派。

拿 TTFTTFTT、k 为 1 走一遍

左边界从 0 起。右边界先吞下标 0、1 的两个 T，少数派都是 0，窗口长到 2。吞下标 2 的 F，T 计 2、F 计 1，少数派 1 不超过 1，长 3。下标 3、4 又是两个 T，少数派仍是那 1 个 F，窗口撑到 5，记录抬到 5。吞下标 5 的 F 时 T 计 4、F 计 2，少数派 2 超过 1：从左边接连踢掉下标 0、1 的 T，少数派仍是 2，再踢下标 2 的 F，F 计回落到 1 才重新合法，左边界停在 3，这段长 3、没破 5。往后吞下标 6、7 的 T，窗口至多回到长 5。扫完答案就是 5。

翻多数派、只缩一格、丢了峰值，都会栽

先算账：右边界把每个字符读进窗口一次、左边界至多踢出一次，每个字符只经手常数次，时间 O(n)；只用几个计数变量，空间 O(1)。真会写坏的有三处。翻转次数取成 max(cntT, cntF)，翻的就成多数派，操作白费、窗口判死太早。超预算时只缩一格就结算也不行，一次踢掉的未必够、少数派可能仍超 k，得循环缩到合法。还有人怕收缩后弄丢好成绩，其实记录存的是历史最大值，窗口变短不回落。边界顺带想清：k 为 0 时答案就是原串最长的同字符段，k 大到够翻满则整串统一。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:
        def f(c: str) -> int:
            cnt = l = 0
            for ch in answerKey:
                cnt += ch == c
                if cnt > k:
                    cnt -= answerKey[l] == c
                    l += 1
            return len(answerKey) - l

        return max(f("T"), f("F"))

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int maxConsecutiveAnswers(string answerKey, int k) {
        int n = answerKey.size();
        auto f = [&](char c) {
            int l = 0, cnt = 0;
            for (char& ch : answerKey) {
                cnt += ch == c;
                if (cnt > k) {
                    cnt -= answerKey[l++] == c;
                }
            }
            return n - l;
        };
        return max(f('T'), f('F'));
    }
};

Java

import java.util.*;
class Solution {
    private String s;
    private int k;

    public int maxConsecutiveAnswers(String answerKey, int k) {
        s = answerKey;
        this.k = k;
        return Math.max(f('T'), f('F'));
    }

    private int f(char c) {
        int l = 0, cnt = 0, n = s.length();
        for (int r = 0; r < n; r++) {
            cnt += s.charAt(r) == c ? 1 : 0;
            if (cnt > k) {
                cnt -= s.charAt(l++) == c ? 1 : 0;
            }
        }
        return n - l;
    }
}