LeetCode 2024. 考试的最大困扰度
题目描述
题意分析
字符串中的每个位置都是
T或F，最多允许修改k个位置，要求修改后最长的一段连续相同字符有多长。可以把这一段变成全T，也可以变成全F，选择能够得到更长区间的一种。修改次数是上限，不必用完；只需要某个连续区间相同，并不要求整条字符串都统一。最终区间之外的位置可以保持原样，所以判断一个候选区间的代价，只需看区间内部有多少字符需要改变。
解法：分别固定目标字符的滑动窗口
核心思路
[!blue]
先固定最终目标字符
target。一个窗口要全部变成它，原本不同的每个字符都必须改一次，原本相同的字符不必改。因此所需次数正好等于窗口内非目标字符的数量changes，窗口可行当且仅当changes <= k。右端加入一个字符时，仅当它不是目标字符才增加
changes。超过预算就逐个移出左端，移出的字符若不是目标才减少代价；移出目标字符不省任何修改次数，可能需要继续移动到某个非目标字符之后，窗口才恢复可行。收缩到刚好可行便停下，保留下当前右端能够对应的最长合法窗口。此前因超预算而丢弃的左端也不必回退：以后继续加入右侧字符只会让相同旧起点的修改代价不减，不可能重新变合法。左右端都只向右移动，能够逐个评估所有可能改善答案的区间。
任何最终相同字符段只有全
T或全F两种情况，分别用同一个窗口过程求最大长度，再取较大者就覆盖了所有答案。两次扫描分别假设一种结果，各自使用完整预算，不是在第一轮真正改完字符后再运行第二轮，原字符串无需修改。
解题步骤
- 编写固定目标字符的窗口过程，初始化左端、当前修改数量和最大长度。
- 从左到右加入字符，非目标字符让修改数量加一。
- 当修改数量超过
k时移出左端，只有移出非目标字符才减少该数量。- 窗口恢复可行后，用当前长度更新答案。
- 分别以
T和F为目标运行，返回两个最大长度中的较大值。
代码实现
class Solution {
public int maxConsecutiveAnswers(String answerKey, int k) {
return Math.max(longest(answerKey, k, 'T'), longest(answerKey, k, 'F'));
}
private int longest(String s, int k, char target) {
int left = 0;
int changes = 0;
int answer = 0;
for (int right = 0; right < s.length(); right++) {
if (s.charAt(right) != target) {
changes++;
}
while (changes > k) {
if (s.charAt(left++) != target) {
changes--;
}
}
answer = Math.max(answer, right - left + 1);
}
return answer;
}
}
func maxConsecutiveAnswers(answerKey string, k int) int {
longest := func(target byte) int {
left, changes, answer := 0, 0, 0
for right := 0; right < len(answerKey); right++ {
if answerKey[right] != target {
changes++
}
for changes > k {
if answerKey[left] != target {
changes--
}
left++
}
answer = max(answer, right-left+1)
}
return answer
}
return max(longest('T'), longest('F'))
}
复杂度分析
- 时间复杂度：
O(n)。每种目标下，每个位置至多加入、移出各一次；两次扫描只增加常数倍开销。- 空间复杂度：
O(1)。只维护窗口边界、修改计数和最大长度，不修改输入或建立辅助数组。
关键点总结
[!green]
- 固定目标后，修改代价就是非目标字符数量，判定直接且精确。
- 超预算才收缩，恢复可行就记录当前右端的最长窗口。
- 两种目标覆盖所有可能结果，二者分别计算后取最大值。
- 预算针对所选区间，不需要修改窗口外的字符。
易错点总结
[!yellow]
- 只尝试变成
T：最佳区间也可能以F为统一目标。- 移出任意字符都减修改数：目标字符原本不需要修改，移出它不会释放预算。
- 修改数等于
k就继续收缩：恰好用完预算仍合法，只有严格超过时才收缩。- 只移动左端一次：左侧可能有多个不消耗预算的字符，需要一直移动到超量被消除。
- 恢复可行前更新答案：会把无法在预算内统一的窗口计入结果。
- 把第一次扫描的预算消耗带入第二次：两次是在比较两种独立方案，应该分别初始化状态。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1004. 最大连续1的个数 III | 中等 | 固定目标为 1 的同一个窗口模型，本题把两个可能目标分别计算。 |
| 424. 替换后的最长重复字符 | 中等 | 扩展到多种字符后可维护窗口最高频次；本题只有两种字符，分别扫描更直接。 |
| 1208. 尽可能使字符串相等 | 中等 | 维护窗口内可消耗的修改预算；本题分别计算统一为两种答案时的窗口，该题预算为对应字符差值之和。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！