2024. 考试的最大困扰度

Problem: 2024. 考试的最大困扰度
尝试了滑动窗口没做出来，这里记录官解的理解

思路

由于字符串中的字符只有t和f，我们可以遍历每种字符最长串的长度，然后取最大值即可。

之前在用滑动窗口做的时候没有想到这个做法，然后就很难想。

给定指定字符，我们可以使用滑动窗口的方法，维护left到right这个区间为更改数量范围内的连续字符串。当right位置的字符不同时，如果更改字符的次数小于k，使用次数加一，否则不断右移left位置，直到找到第一个更改的地方为止。在right不断右移的过程中，记录能够到达的最大长度。

复杂度

• 时间复杂度: $O(n)$，n为字符串长度，遍历字符串两次。
• 空间复杂度: $O(1)$。

Code

class Solution {
    public int maxConsecutiveAnswers(String answerKey, int k) {
        return Math.max(maxConsecutiveChar(answerKey, k, 'T'), maxConsecutiveChar(answerKey, k, 'F'));
    }
    
    public int maxConsecutiveChar(String answerKey, int k, char ch) {
        int n = answerKey.length();
        int ans = 0;
        for (int left = 0, right = 0, sum = 0; right < n; right++) {
            sum += answerKey.charAt(right) != ch ? 1 : 0;
            while (sum > k) {
                sum -= answerKey.charAt(left++) != ch ? 1 : 0;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}