2024. Maximize the Confusion of an Exam

Description

A teacher is writing a test with n true/false questions, with 'T' denoting true and 'F' denoting false. He wants to confuse the students by maximizing the number of consecutive questions with the same answer (multiple trues or multiple falses in a row).

You are given a string answerKey, where answerKey[i] is the original answer to the ith question. In addition, you are given an integer k, the maximum number of times you may perform the following operation:

• Change the answer key for any question to 'T' or 'F' (i.e., set answerKey[i] to 'T' or 'F').

Return the maximum number of consecutive 'T's or 'F's in the answer key after performing the operation at most k times.

 

Example 1:

Input: answerKey = "TTFF", k = 2
Output: 4
Explanation: We can replace both the 'F's with 'T's to make answerKey = "TTTT".
There are four consecutive 'T's.

Example 2:

Input: answerKey = "TFFT", k = 1
Output: 3
Explanation: We can replace the first 'T' with an 'F' to make answerKey = "FFFT".
Alternatively, we can replace the second 'T' with an 'F' to make answerKey = "TFFF".
In both cases, there are three consecutive 'F's.

Example 3:

Input: answerKey = "TTFTTFTT", k = 1
Output: 5
Explanation: We can replace the first 'F' to make answerKey = "TTTTTFTT"
Alternatively, we can replace the second 'F' to make answerKey = "TTFTTTTT". 
In both cases, there are five consecutive 'T's.

 

Constraints:

• n == answerKey.length
• 1 <= n <= 5 * 104
• answerKey[i] is either 'T' or 'F'
• 1 <= k <= n

Solutions

Solution 1: Two Pointers

We design a function $f(c)$, which represents the longest length of consecutive characters under the condition that at most $k$ characters $c$ are replaced, where $c$ can be 'T' or 'F'. The answer is $\max(f('T'), f('F'))$.

We use two pointers to maintain a range $[j, i]$ such that the number of characters $c$ in the range does not exceed $k$. When the number of characters $c$ in the range exceeds $k$, we move the left pointer $j$ until the number of characters $c$ in the range does not exceed $k$, then update the answer $ans = \max(ans, i - j + 1)$.

The time complexity is $O(n)$, where $n$ is the length of the string. The space complexity is $O(1)$.

Python3JavaC++GoTypeScriptRust

class Solution:
    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:
        def f(c: str) -> int:
            cnt = j = 0
            ans = 0
            for i, ch in enumerate(answerKey):
                cnt += ch == c
                while cnt > k:
                    cnt -= answerKey[j] == c
                    j += 1
                ans = max(ans, i - j + 1)
            return ans

        return max(f("T"), f("F"))

class Solution {
    private char[] s;
    private int k;

    public int maxConsecutiveAnswers(String answerKey, int k) {
        s = answerKey.toCharArray();
        this.k = k;
        return Math.max(f('T'), f('F'));
    }

    private int f(char c) {
        int cnt = 0, ans = 0;
        for (int i = 0, j = 0; i < s.length; ++i) {
            cnt += s[i] == c ? 1 : 0;
            while (cnt > k) {
                cnt -= s[j] == c ? 1 : 0;
                ++j;
            }
            ans = Math.max(ans, i - j + 1);
        }
        return ans;
    }
}

class Solution {
public:
    int maxConsecutiveAnswers(string answerKey, int k) {
        auto f = [&](char c) {
            int ans = 0, cnt = 0;
            for (int i = 0, j = 0; i < answerKey.size(); ++i) {
                cnt += answerKey[i] == c;
                while (cnt > k) {
                    cnt -= answerKey[j++] == c;
                }
                ans = max(ans, i - j + 1);
            }
            return ans;
        };
        return max(f('T'), f('F'));
    }
};

func maxConsecutiveAnswers(answerKey string, k int) int {
    f := func(c byte) int {
        var ans, cnt, j int
        for i := range answerKey {
            if answerKey[i] == c {
                cnt++
            }
            for cnt > k {
                if answerKey[j] == c {
                    cnt--
                }
                j++
            }
            ans = max(ans, i-j+1)
        }
        return ans
    }
    return max(f('T'), f('F'))
}

function maxConsecutiveAnswers(answerKey: string, k: number): number {
    const n = answerKey.length;
    const f = (c: string): number => {
        let [ans, cnt, j] = [0, 0, 0];
        for (let i = 0; i < n; ++i) {
            cnt += answerKey[i] === c ? 0 : 1;
            while (cnt > k) {
                cnt -= answerKey[j++] === c ? 0 : 1;
            }
            ans = Math.max(ans, i - j + 1);
        }
        return ans;
    };
    return Math.max(f('T'), f('F'));
}

impl Solution {
    pub fn max_consecutive_answers(answer_key: String, k: i32) -> i32 {
        let s: Vec<char> = answer_key.chars().collect();
        let f = |c: char| -> i32 {
            let mut cnt = 0;
            let mut j = 0;
            let mut ans = 0;
            for i in 0..s.len() {
                cnt += if s[i] == c { 1 } else { 0 };
                while cnt > k {
                    cnt -= if s[j] == c { 1 } else { 0 };
                    j += 1;
                }
                ans = ans.max((i - j + 1) as i32);
            }
            ans
        };
        f('T').max(f('F'))
    }
}

Comments