题目描述
思路解析
一句话答案：LeetCode 2024 考试的最大困扰度用滑动窗口：一串只有 T 和 F，最多翻 k 次，求最长同字符段。窗口内少数派个数不超过 k 就能整段刷成一色，右扩左缩扫一遍即可。时间 O(n)、空间 O(1)。
一串 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 大到够翻满则整串统一。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这一句:窗口里少数派的个数就是要翻转的次数,这个次数不超过 k,窗口就合法。少数派超了就从左边缩,缩到刚好合法为止。下面每一帧都在套这句话。
先把整串摆出来,下标从 0 到 7 依次是 T T F T T F T T。我们要从左往右滑一个窗口,窗口里数着 T 和 F 各多少个。右边这张小面板就是窗口内的统计,现在窗口还没开张,两个计数都是 0。开始读入字符。
把右端下标 0 的字符 T 读进窗口,它的计数加一。现在窗口里 T 有 1 个,F 有 0 个,少数派是 0 个。少数派 0 ≤ k = 1,窗口还合法,先放着,等下结算。
结算这一步。窗口 [0..0] 现在合法,大小是 1,里面翻掉少数派的 0 个字符就能全部相同。它比之前见过的都长,刷新历史最长 ans = 1。
把右端下标 1 的字符 T 读进窗口,它的计数加一。现在窗口里 T 有 2 个,F 有 0 个,少数派是 0 个。少数派 0 ≤ k = 1,窗口还合法,先放着,等下结算。
结算这一步。窗口 [0..1] 现在合法,大小是 2,里面翻掉少数派的 0 个字符就能全部相同。它比之前见过的都长,刷新历史最长 ans = 2。
把右端下标 2 的字符 F 读进窗口,它的计数加一。现在窗口里 T 有 2 个,F 有 1 个,少数派是 1 个。少数派 1 ≤ k = 1,窗口还合法,先放着,等下结算。
结算这一步。窗口 [0..2] 现在合法,大小是 3,里面翻掉少数派的 1 个字符就能全部相同。它比之前见过的都长,刷新历史最长 ans = 3。
把右端下标 3 的字符 T 读进窗口,它的计数加一。现在窗口里 T 有 3 个,F 有 1 个,少数派是 1 个。少数派 1 ≤ k = 1,窗口还合法,先放着,等下结算。
结算这一步。窗口 [0..3] 现在合法,大小是 4,里面翻掉少数派的 1 个字符就能全部相同。它比之前见过的都长,刷新历史最长 ans = 4。
把右端下标 4 的字符 T 读进窗口,它的计数加一。现在窗口里 T 有 4 个,F 有 1 个,少数派是 1 个。少数派 1 ≤ k = 1,窗口还合法,先放着,等下结算。
结算这一步。窗口 [0..4] 现在合法,大小是 5,里面翻掉少数派的 1 个字符就能全部相同。它比之前见过的都长,刷新历史最长 ans = 5。
把右端下标 5 的字符 F 读进窗口,它的计数加一。现在窗口里 T 有 4 个,F 有 2 个,少数派是 2 个。少数派 2 已经 > k = 1,窗口暂时不合法,得从左边缩一缩。
窗口不合法,从最左边把下标 0 的 T 踢出去,左指针右移到 1。现在窗口里 T 有 3 个,F 有 2 个,少数派 2 个。少数派还是 2 个,仍然 > k = 1,继续往右踢。
窗口不合法,从最左边把下标 1 的 T 踢出去,左指针右移到 2。现在窗口里 T 有 2 个,F 有 2 个,少数派 2 个。少数派还是 2 个,仍然 > k = 1,继续往右踢。
窗口不合法,从最左边把下标 2 的 F 踢出去,左指针右移到 3。现在窗口里 T 有 2 个,F 有 1 个,少数派 1 个。少数派 1 ≤ k = 1,终于合法了,可以停下来结算。
结算这一步。窗口 [3..5] 现在合法,大小是 3,里面翻掉少数派的 1 个字符就能全部相同。它没有超过历史最长 5,ans 保持不动,窗口继续往右滑。
把右端下标 6 的字符 T 读进窗口,它的计数加一。现在窗口里 T 有 3 个,F 有 1 个,少数派是 1 个。少数派 1 ≤ k = 1,窗口还合法,先放着,等下结算。
结算这一步。窗口 [3..6] 现在合法,大小是 4,里面翻掉少数派的 1 个字符就能全部相同。它没有超过历史最长 5,ans 保持不动,窗口继续往右滑。
把右端下标 7 的字符 T 读进窗口,它的计数加一。现在窗口里 T 有 4 个,F 有 1 个,少数派是 1 个。少数派 1 ≤ k = 1,窗口还合法,先放着,等下结算。
结算这一步。窗口 [3..7] 现在合法,大小是 5,里面翻掉少数派的 1 个字符就能全部相同。它没有超过历史最长 5,ans 保持不动,窗口继续往右滑。
整串滑完了。见过的最长合法窗口是 [0..4],也就是 TTFTT 这一段。它里面只有 1 个 F,把这个 F 翻成 T,整段就变成 5 个连续的 T,正好用掉 1 次操作。所以答案就是 5,跟开头看出来的对上了。
边界想清:k 为 0 时答案等于原串最长同字符段、k 够大时能翻成全长、本来全相同则直接是全长。
面试重点:变长窗口加少数派受限、和最大连续 1 的个数 III 同源、两趟法与单窗口法等价。
参考代码
from __future__ import annotationsfrom 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"))复杂度
- 时间：O(n)，n 是字符串长度。单窗口法里每个下标最多被右指针读入一次、被左指针踢出一次,合计每个字符常数次操作;参考代码的两趟法各扫一遍,仍是线性
- 空间：O(1)，只用到 cntT、cntF、l、ans 这几个计数变量,不随字符串变长而增加。参考代码三种语言都直接在原字符串上按下标读字符(Java 用 charAt),不额外开数组,空间同为常数
易错点
面试追问把动画讲成自己的话
追问这题的核心结构是什么?
追问它和最大连续 1 的个数 III 是一回事吗?
追问参考代码为什么写成两趟?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
分配给商店的最多商品的最小值
LeetCode 2064 · 中等 · 沿着 二分套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题