Maximize the Confusion of an Exam

Problem Statement

In the given scenario, a teacher is preparing a test comprising n true/false questions represented by the characters 'T' for true and 'F' for false. The objective is to manipulate the sequence of answers by a specified number of operations to maximize the length of consecutive identical answers, which could either be all 'T's or all 'F's. The allowable operation, which can be performed a maximum of k times, involves changing any question's answer from 'T' to 'F' or vice versa. The challenge is to determine the maximum number of consecutive identical answers that can be achieved by utilizing up to k operations.

Examples

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

Approach and Intuition

The goal is to maximize contiguous segments of either 'T's or 'F's. Considering the constraints that operations can be used up to k times, we can use a sliding window technique with two pointers to solve this problem efficiently. Here's how we can break down the process:

1. Use two pointers, left and right, to represent the current window of consecutive answers within the answerKey.
2. Expand the window by moving the right pointer and counting the number of either 'T' or 'F' within the window.
3. If the count of characters that need to be changed exceeds k, adjust the left pointer to shrink the window until the count is at or below k.
4. The length of the window (i.e., right - left + 1) will give the maximum consecutive sequence for the current character focus.
5. Repeat this process twice - once focusing on maximizing 'T's and once on 'F's.
6. The larger of the two results from the above iterations will be the maximum number of consecutive identical answers that can be achieved.

From the examples provided:

• For Example 1, changing both 'F's to 'T's leads to "TTTT", achieving 4 consecutive 'T's with 2 changes.
• For Example 2, changing one 'T' to 'F' either way maximizes consecutive 'F's to 3, demonstrating the flexibility in selecting which character to optimize.
• In Example 3, changing one 'F' at different positions can optimize up to 5 consecutive 'T's, illustrating how strategic changes in larger sequences can yield significant stretches of identical answers.

By using this sliding window technique, we efficiently explore and adjust segments of the answerKey to find the optimal length of consecutive answers, ensuring we do not exceed the allowed k changes.

Solutions

class Solution {
public:
    int getMaxAnswerStreak(string answerKey, int k) {
        int maxStreak = 0;
        unordered_map<char, int> countLetters;
            
        for (int r = 0; r < answerKey.size(); r++) {
            countLetters[answerKey[r]]++;
            int smallest = min(countLetters['T'], countLetters['F']);
                
            if (smallest <= k) {
                maxStreak++;
            } else {
                countLetters[answerKey[r - maxStreak]]--;
            }
        }
    
        return maxStreak;
    }
};