# Maximize the Confusion of an Exam
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximize-the-confusion-of-an-exam)
Canonical: https://scaleengineer.com/dsa/problems/maximize-the-confusion-of-an-exam
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** String
**Companies:** [Arcesium](https://scaleengineer.com/companies/arcesium)
---
## Problem
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`

# Approaches
## Brute Force Approach
This approach involves checking every possible contiguous subarray within the `answerKey`. For each subarray, we count the number of 'T's and 'F's. If the count of either character is less than or equal to `k`, it means we can make the entire subarray uniform by performing at most `k` changes. We keep track of the maximum length of such a valid subarray.
**Time:** O(N^2), where N is the length of `answerKey`. The nested loops iterate through all O(N^2) subarrays. · **Space:** O(1), as we only use a few variables to store counts and pointers, regardless of the input size.
**Pros:** Simple to understand and implement.; Correct for small input sizes.
**Cons:** Highly inefficient due to its O(N^2) time complexity.; Will result in a 'Time Limit Exceeded' (TLE) error on platforms like LeetCode for the given constraints.
### Explanation
We use two nested loops to define the start (`i`) and end (`j`) of each subarray. The outer loop iterates from the first character to the last to set the starting point. The inner loop expands the subarray from the starting point to the end of the string. Inside the inner loop, we maintain counts of 'T's and 'F's for the current subarray `[i, j]`. For each subarray, we check if it can be made entirely of 'T's (by changing at most `k` 'F's) or entirely of 'F's (by changing at most `k` 'T's). If this is possible, we update our `maxLength` with the current subarray's length (`j - i + 1`). After checking all O(N^2) subarrays, `maxLength` will hold the result.

```java
class Solution {
    public int maxConsecutiveAnswers(String answerKey, int k) {
        int n = answerKey.length();
        int maxLength = 0;
        if (k >= n / 2) {
            return n;
        }
        for (int i = 0; i < n; i++) {
            int countT = 0;
            int countF = 0;
            for (int j = i; j < n; j++) {
                if (answerKey.charAt(j) == 'T') {
                    countT++;
                } else {
                    countF++;
                }
                if (countT <= k || countF <= k) {
                    maxLength = Math.max(maxLength, j - i + 1);
                }
            }
        }
        return maxLength;
    }
}
```
### Algorithm
- Initialize `maxLength = 0`.
- Use a nested loop structure. The outer loop with index `i` determines the start of a potential subarray, and the inner loop with index `j` determines the end.
- For each subarray `answerKey[i...j]`, count the number of 'T's (`countT`) and 'F's (`countF`).
- A subarray can be made uniform if the number of characters to change is at most `k`. This means either `countT <= k` (to make it all 'F's) or `countF <= k` (to make it all 'T's).
- If the condition `countT <= k || countF <= k` is met, the current subarray of length `j - i + 1` is a valid candidate for the maximum length.
- Update `maxLength = max(maxLength, j - i + 1)`.
- After iterating through all possible subarrays, return `maxLength`.

## Binary Search on Answer Length
This approach reframes the problem from "what is the maximum length?" to "is it possible to achieve a length of `L`?". This "yes/no" question is easier to answer and has a monotonic property: if a length `L` is possible, any length less than `L` is also possible. This allows us to use binary search on the possible answer lengths, from 1 to `n`.
**Time:** O(N log N). The binary search takes O(log N) steps. In each step, we call `isPossible`, which takes O(N) time to slide the window across the string. · **Space:** O(1), as the algorithm uses a constant amount of extra space.
**Pros:** Significantly more efficient than brute force.; Guaranteed to pass within the time limits for the given constraints.
**Cons:** More complex to implement compared to the brute-force or the final sliding window approach.; Not the most optimal solution, as a linear time solution exists.
### Explanation
We perform a binary search on the answer, which is the length of the consecutive sequence. The search space is from `1` to `n`. For each `mid` value (a potential length) in our binary search, we need a function `isPossible(length)` to check if a consecutive sequence of this `length` can be formed with at most `k` changes. This function itself uses a fixed-size sliding window of size `length`. It slides this window across the `answerKey` and checks if any window can be made all 'T's (i.e., has `k` or fewer 'F's) or all 'F's (i.e., has `k` or fewer 'T's). The sliding window check for a fixed length is an O(N) operation. Since this check is inside a binary search, the total time complexity is O(N log N).

```java
class Solution {
    public int maxConsecutiveAnswers(String answerKey, int k) {
        int n = answerKey.length();
        int low = 1, high = n;
        int ans = 0;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (isPossible(answerKey, k, mid)) {
                ans = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return ans;
    }

    private boolean isPossible(String answerKey, int k, int len) {
        return check(answerKey, k, len, 'T') || check(answerKey, k, len, 'F');
    }

    private boolean check(String answerKey, int k, int len, char targetChar) {
        int n = answerKey.length();
        int changesNeeded = 0;
        for (int i = 0; i < len; i++) {
            if (answerKey.charAt(i) != targetChar) {
                changesNeeded++;
            }
        }
        if (changesNeeded <= k) return true;

        for (int i = len; i < n; i++) {
            if (answerKey.charAt(i) != targetChar) changesNeeded++;
            if (answerKey.charAt(i - len) != targetChar) changesNeeded--;
            if (changesNeeded <= k) return true;
        }
        return false;
    }
}
```
### Algorithm
- The core idea is to binary search for the answer (the maximum length). The possible lengths range from `1` to `n`.
- Define a search space with `low = 1` and `high = n`.
- In each step of the binary search, pick a `mid` length and check if it's possible to form a consecutive sequence of this length using a helper function `isPossible(mid)`.
- The `isPossible(length)` function uses a fixed-size sliding window of the given `length` to check if any such window can be made uniform with at most `k` changes. This check is done for both 'T' and 'F'.
- To check for 'T's, we slide a window of size `length` and see if any window contains `<= k` 'F's. This check can be done in O(N) time.
- If `isPossible(mid)` is true, it means a length of `mid` is achievable. We store it as a potential answer (`ans = mid`) and try for a larger length by setting `low = mid + 1`.
- If `isPossible(mid)` is false, the length `mid` is too large, so we search for a smaller length by setting `high = mid - 1`.
- The loop continues until `low > high`, and the final `ans` is returned.

## Optimal Sliding Window
This is the most efficient approach. The problem can be simplified to finding the longest subarray that contains at most `k` of the "other" character. We can solve this for both 'T' and 'F' and take the maximum. For example, to find the maximum consecutive 'T's, we find the longest subarray with at most `k` 'F's. This is a classic sliding window problem that can be solved in linear time.
**Time:** O(N), where N is the length of `answerKey`. Each pointer, `left` and `right`, traverses the array at most once. Since we run this process twice (once for 'T' and once for 'F'), the total complexity is O(N) + O(N) = O(N). · **Space:** O(1). We only use a few variables for pointers and counts.
**Pros:** Most efficient solution with linear time complexity.; Elegant and relatively straightforward to implement once the sliding window concept is understood.
**Cons:** It might be slightly less intuitive at first glance than the brute-force approach.
### Explanation
We can solve this problem by running the sliding window algorithm twice: once to find the longest sequence of 'T's and once for 'F's. The final answer is the maximum of these two results. Let's describe the process for finding the longest sequence of 'T's. We use a variable-sized window, defined by `left` and `right` pointers. We expand the window by moving `right`. We keep a count of 'F's in the window. If this count exceeds `k`, we shrink the window from the left until the count is at most `k` again. At each step, we update our maximum length with the current valid window's size. This ensures we find the longest valid subarray in a single pass.

```java
class Solution {
    public int maxConsecutiveAnswers(String answerKey, int k) {
        // Find the max length for making all 'T's
        int maxForT = findMaxForChar(answerKey, k, 'T');
        // Find the max length for making all 'F's
        int maxForF = findMaxForChar(answerKey, k, 'F');
        // The answer is the maximum of the two scenarios
        return Math.max(maxForT, maxForF);
    }

    private int findMaxForChar(String answerKey, int k, char targetChar) {
        int n = answerKey.length();
        int left = 0;
        int maxLength = 0;
        int changes = 0; // Count of the character to be changed

        for (int right = 0; right < n; right++) {
            // If the current character is not our target, we need to change it
            if (answerKey.charAt(right) != targetChar) {
                changes++;
            }

            // If we have used more than k changes, the window is invalid.
            // Shrink the window from the left until it's valid again.
            while (changes > k) {
                if (answerKey.charAt(left) != targetChar) {
                    changes--;
                }
                left++;
            }

            // The window [left, right] is now a valid window.
            // Update the max length found so far.
            maxLength = Math.max(maxLength, right - left + 1);
        }
        return maxLength;
    }
}
```
### Algorithm
- The problem is broken into two subproblems: find the max consecutive 'T's, and find the max consecutive 'F's. The final answer is the maximum of the two.
- To solve a subproblem (e.g., for 'T's), we find the longest subarray with at most `k` 'F's.
- This is done using a variable-sized sliding window with `left` and `right` pointers.
- Initialize `left = 0`, `maxLength = 0`, and a counter for the character we want to change (e.g., `f_count = 0`).
- Iterate `right` from `0` to `n-1`, expanding the window.
- If `answerKey[right]` is an 'F', increment `f_count`.
- If `f_count` exceeds `k`, the window is invalid. Shrink the window from the left by incrementing `left` until the window is valid again. While shrinking, if `answerKey[left]` was an 'F', decrement `f_count`.
- After each expansion of `right`, the window `[left, right]` is valid. Update `maxLength = max(maxLength, right - left + 1)`.
- Repeat this process for the other character ('F') and return the overall maximum length.

# Solutions
### Java

```java
class Solution { public int maxConsecutiveAnswers ( String answerKey , int k ) { return Math . max ( get ( 'T' , k , answerKey ), get ( 'F' , k , answerKey )); } public int get ( char c , int k , String answerKey ) { int l = 0 , r = 0 ; while ( r < answerKey . length ()) { if ( answerKey . charAt ( r ++) == c ) { -- k ; } if ( k < 0 && answerKey . charAt ( l ++) == c ) { ++ k ; } } return r - l ; } }
```

### CPP

```cpp
class Solution { public: int maxConsecutiveAnswers ( string answerKey , int k ) { return max ( get ( 'T' , k , answerKey ), get ( 'F' , k , answerKey )); } int get ( char c , int k , string & answerKey ) { int l = 0 , r = 0 ; while ( r < answerKey . size ()) { if ( answerKey [ r ++ ] == c ) -- k ; if ( k < 0 && answerKey [ l ++ ] == c ) ++ k ; } return r - l ; } };
```

### Python

```python
class Solution : def maxConsecutiveAnswers ( self , answerKey : str , k : int ) -> int : def get ( c , k ): l = r = - 1 while r < len ( answerKey ) - 1 : r += 1 if answerKey [ r ] == c : k -= 1 if k < 0 : l += 1 if answerKey [ l ] == c : k += 1 return r - l return max ( get ( 'T' , k ), get ( 'F' , k ))
```