LeetCode 2024. 考试的最大困扰度【不定长滑窗】1643

本文属于「征服LeetCode」系列文章之一，这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁，本系列将至少持续到刷完所有无锁题之日为止；由于LeetCode还在不断地创建新题，本系列的终止日期可能是永远。在这一系列刷题文章中，我不仅会讲解多种解题思路及其优化，还会用多种编程语言实现题解，涉及到通用解法时更将归纳总结出相应的算法模板。

为了方便在PC上运行调试、分享代码文件，我还建立了相关的仓库：https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中，你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等，还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解，还可以一同分享给他人。

由于本系列文章的内容随时可能发生更新变动，欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。

一位老师正在出一场由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 * 10^4
• answerKey[i]要么是'T'，要么是'F'
• 1 <= k <= n

解法 不定长滑窗（求最长但越短越容易合法）

求a n s w e r K e y answerKeyanswerKey的一个最长子串，包含至多k kk个T \text{T}T或者至多k kk个F \text{F}F。

由于子串越长，越无法满足要求，有单调性，可以用滑动窗口解决。

1. 遍历a n s w e r K e y answerKeyanswerKey，枚举子串右端点r i g h t rightright，同时维护最小左端点l e f t leftleft以及子串中的字符个数c n t cntcnt。
2. 把a n s w e r K e y [ r i g h t ] answerKey[right]answerKey[right]的出现次数加一。
3. 如果T \text{T}T和F \text{F}F的出现次数都超过k kk，那么必须不断移动左端点l e f t leftleft，同时减少a n s w e r K e y [ l e f t ] answerKey[left]answerKey[left]的出现次数，直到T \text{T}T和F \text{F}F的出现次数至少有一个≤ k ≤k≤k。
4. 循环结束后，说明子串右端点在r i g h t rightright时，对应的最小左端点为l e f t leftleft，用子串长度r i g h t − l e f t + 1 right−left+1right−left+1更新答案的最大值。
5. 遍历a n s w e r K e y answerKeyanswerKey结束后，返回答案。

代码实现时，由于T \text{T}T和F \text{F}F的 ASCII 值除以 2 后的奇偶性不同，也就是它们二进制的次低位不同，可以改为统计二进制次低位。

classSolution{publicintmaxConsecutiveAnswers(StringanswerKey,intk){char[]s=answerKey.toCharArray();intans=0;intleft=0;int[]cnt=newint[2];for(intright=0;right<s.length;right++){cnt[s[right]>>1&1]++;while(cnt[0]>k&&cnt[1]>k){cnt[s[left]>>1&1]--;left++;}ans=Math.max(ans,right-left+1);}returnans;}}

classSolution{public:intmaxConsecutiveAnswers(string answerKey,intk){intans=0,left=0,cnt[2]{};for(intright=0;right<answerKey.length();right++){cnt[answerKey[right]>>1&1]++;while(cnt[0]>k&&cnt[1]>k){cnt[answerKey[left]>>1&1]--;left++;}ans=max(ans,right-left+1);}returnans;}};

classSolution:defmaxConsecutiveAnswers(self,answerKey:str,k:int)->int:ans=left=0cnt=defaultdict(int)forright,chinenumerate(answerKey):cnt[ch]+=1whilecnt['T']>kandcnt['F']>k:cnt[answerKey[left]]-=1left+=1ans=max(ans,right-left+1)returnans

funcmaxConsecutiveAnswers(answerKeystring,kint)(ansint){cnt:=[2]int{}left:=0forright,ch:=rangeanswerKey{cnt[ch>>1&1]++forcnt[0]>k&&cnt[1]>k{cnt[answerKey[left]>>1&1]--left++}ans=max(ans,right-left+1)}return}

implSolution{pubfnmax_consecutive_answers(answer_key:String,k:i32)->i32{lets=answer_key.as_bytes();letmutans=0;letmutleft=0;letmutcnt=[0,0];for(right,&ch)ins.iter().enumerate(){cnt[(ch>>1&1)asusize]+=1;whilecnt[0]>k&&cnt[1]>k{cnt[(s[left]>>1&1)asusize]-=1;left+=1;}ans=ans.max(right-left+1);}ansas_}}

varmaxConsecutiveAnswers=function(answerKey,k){letans=0,left=0;constcnt={'T':0,'F':0};for(letright=0;right<answerKey.length;right++){cnt[answerKey[right]]++;while(cnt['T']>k&&cnt['F']>k){cnt[answerKey[left]]--;left++}ans=Math.max(ans,right-left+1);}returnans;};// 写法2varmaxConsecutiveAnswers=function(answerKey,k){letans=0,left=0;constcnt=[0,0];for(letright=0;right<answerKey.length;right++){cnt[answerKey[right].charCodeAt(0)>>1&1]++;while(cnt[0]>k&&cnt[1]>k){cnt[answerKey[left].charCodeAt(0)>>1&1]--;left++;}ans=Math.max(ans,right-left+1);}returnans;};

#defineMAX(a,b)((b)>(a)?(b):(a))intmaxConsecutiveAnswers(char*answerKey,intk){intans=0,left=0,cnt[2]={};for(intright=0;answerKey[right];right++){cnt[answerKey[right]>>1&1]++;while(cnt[0]>k&&cnt[1]>k){cnt[answerKey[left]>>1&1]--;left++;}ans=MAX(ans,right-left+1);}returnans;}

复杂度分析：

• 时间复杂度：O ( n ) O(n)O(n)。
• 空间复杂度：O ( n ) O(n)O(n)。

思考题

把子串改为子序列该怎么做？