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

这道题到底在问什么

输入

answerKey="TTFTTFTT", k=1

输出

5

输入

answerKey="TTFF", k=2

输出

4

输入

answerKey="TFFT", k=0

输出

2

最优解：一步一步想明白

1. 3记牢这一句:窗口里少数派的个数就是要翻转的次数,这个次数不超过 k,窗口就合法。少数派超了就从左边缩,缩到刚好合法为止。下面每一帧都在套这句话。
2. 4先把整串摆出来,下标从 0 到 7 依次是 T T F T T F T T。我们要从左往右滑一个窗口,窗口里数着 T 和 F 各多少个。右边这张小面板就是窗口内的统计,现在窗口还没开张,两个计数都是 0。开始读入字符。
3. 5把右端下标 0 的字符 T 读进窗口,它的计数加一。现在窗口里 T 有 1 个,F 有 0 个,少数派是 0 个。少数派 0 ≤ k = 1,窗口还合法,先放着,等下结算。
4. 6结算这一步。窗口 [0..0] 现在合法,大小是 1,里面翻掉少数派的 0 个字符就能全部相同。它比之前见过的都长,刷新历史最长 ans = 1。
5. 7把右端下标 1 的字符 T 读进窗口,它的计数加一。现在窗口里 T 有 2 个,F 有 0 个,少数派是 0 个。少数派 0 ≤ k = 1,窗口还合法,先放着,等下结算。
6. 8结算这一步。窗口 [0..1] 现在合法,大小是 2,里面翻掉少数派的 0 个字符就能全部相同。它比之前见过的都长,刷新历史最长 ans = 2。
7. 9把右端下标 2 的字符 F 读进窗口,它的计数加一。现在窗口里 T 有 2 个,F 有 1 个,少数派是 1 个。少数派 1 ≤ k = 1,窗口还合法,先放着,等下结算。
8. 10结算这一步。窗口 [0..2] 现在合法,大小是 3,里面翻掉少数派的 1 个字符就能全部相同。它比之前见过的都长,刷新历史最长 ans = 3。
9. 11把右端下标 3 的字符 T 读进窗口,它的计数加一。现在窗口里 T 有 3 个,F 有 1 个,少数派是 1 个。少数派 1 ≤ k = 1,窗口还合法,先放着,等下结算。
10. 12结算这一步。窗口 [0..3] 现在合法,大小是 4,里面翻掉少数派的 1 个字符就能全部相同。它比之前见过的都长,刷新历史最长 ans = 4。
11. 13把右端下标 4 的字符 T 读进窗口,它的计数加一。现在窗口里 T 有 4 个,F 有 1 个,少数派是 1 个。少数派 1 ≤ k = 1,窗口还合法,先放着,等下结算。
12. 14结算这一步。窗口 [0..4] 现在合法,大小是 5,里面翻掉少数派的 1 个字符就能全部相同。它比之前见过的都长,刷新历史最长 ans = 5。
13. 15把右端下标 5 的字符 F 读进窗口,它的计数加一。现在窗口里 T 有 4 个,F 有 2 个,少数派是 2 个。少数派 2 已经 > k = 1,窗口暂时不合法,得从左边缩一缩。
14. 16窗口不合法,从最左边把下标 0 的 T 踢出去,左指针右移到 1。现在窗口里 T 有 3 个,F 有 2 个,少数派 2 个。少数派还是 2 个,仍然 > k = 1,继续往右踢。
15. 17窗口不合法,从最左边把下标 1 的 T 踢出去,左指针右移到 2。现在窗口里 T 有 2 个,F 有 2 个,少数派 2 个。少数派还是 2 个,仍然 > k = 1,继续往右踢。
16. 18窗口不合法,从最左边把下标 2 的 F 踢出去,左指针右移到 3。现在窗口里 T 有 2 个,F 有 1 个,少数派 1 个。少数派 1 ≤ k = 1,终于合法了,可以停下来结算。
17. 19结算这一步。窗口 [3..5] 现在合法,大小是 3,里面翻掉少数派的 1 个字符就能全部相同。它没有超过历史最长 5,ans 保持不动,窗口继续往右滑。
18. 20把右端下标 6 的字符 T 读进窗口,它的计数加一。现在窗口里 T 有 3 个,F 有 1 个,少数派是 1 个。少数派 1 ≤ k = 1,窗口还合法,先放着,等下结算。
19. 21结算这一步。窗口 [3..6] 现在合法,大小是 4,里面翻掉少数派的 1 个字符就能全部相同。它没有超过历史最长 5,ans 保持不动,窗口继续往右滑。
20. 22把右端下标 7 的字符 T 读进窗口,它的计数加一。现在窗口里 T 有 4 个,F 有 1 个,少数派是 1 个。少数派 1 ≤ k = 1,窗口还合法,先放着,等下结算。
21. 23结算这一步。窗口 [3..7] 现在合法,大小是 5,里面翻掉少数派的 1 个字符就能全部相同。它没有超过历史最长 5,ans 保持不动,窗口继续往右滑。
22. 24整串滑完了。见过的最长合法窗口是 [0..4],也就是 TTFTT 这一段。它里面只有 1 个 F,把这个 F 翻成 T,整段就变成 5 个连续的 T,正好用掉 1 次操作。所以答案就是 5,跟开头看出来的对上了。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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"))

#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'));
    }
};

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;
    }
}

复杂度

面试官可能追问