{x}
blog image

Maximize the Confusion of an Exam

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

Solution Explanation: Maximize the Confusion of an Exam

The problem asks to find the maximum number of consecutive 'T's or 'F's in a string answerKey after changing at most k characters. The solution uses a sliding window approach, optimized for efficiency.

Approach: Sliding Window Optimization

Instead of brute-forcing all possible combinations of changes, the sliding window technique efficiently tracks the longest consecutive sequence. The core idea is that we process the string once for 'T's and once for 'F's, maximizing the consecutive count for each character independently.

The algorithm works as follows:

  1. Helper Function f(c): A helper function f(c) is defined to calculate the maximum length of consecutive characters c ('T' or 'F') achievable with at most k changes. This function uses a sliding window.

  2. Sliding Window Mechanics:

    • A window is maintained using two pointers: l (left) and implicitly the current index as the right pointer.
    • cnt tracks the number of characters different from c within the window. This is equivalent to the number of characters that would need to be changed to make them c.
    • The window expands until cnt exceeds k. When this happens, the left pointer l is moved right to shrink the window and reduce cnt until it's at most k.

  3. Maximum Length: The length of the final valid window after the iteration represents the maximum consecutive count of c.

  4. Final Result: The function returns the maximum of the lengths obtained for 'T' and 'F', representing the overall solution.

Time and Space Complexity

  • Time Complexity: O(n), where n is the length of answerKey. The string is traversed twice (once for 'T' and once for 'F'), each traversal taking linear time.
  • Space Complexity: O(1). The algorithm uses a constant amount of extra space to store variables like cnt, l, and the character c.

Code Examples (Python3, Java, C++, Go, TypeScript, Rust)

The code implementations below reflect the sliding window approach described above. Each language version follows the same basic logic but with syntax specific to the language.

Python3:

class Solution:
    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:
        def f(c: str) -> int:
            cnt = l = 0
            for r, ch in enumerate(answerKey):
                cnt += ch != c
                while cnt > k:
                    cnt -= answerKey[l] != c
                    l += 1
            return len(answerKey) - l
 
        return max(f("T"), f("F"))

Java:

class Solution {
    public int maxConsecutiveAnswers(String answerKey, int k) {
        int maxLen = 0;
        maxLen = Math.max(maxLen, helper(answerKey, k, 'T'));
        maxLen = Math.max(maxLen, helper(answerKey, k, 'F'));
        return maxLen;
    }
 
    private int helper(String s, int k, char c) {
        int l = 0;
        int cnt = 0;
        for (int r = 0; r < s.length(); r++) {
            if (s.charAt(r) != c) cnt++;
            while (cnt > k) {
                if (s.charAt(l++) != c) cnt--;
            }
        }
        return s.length() - l;
    }
}

C++:

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

Go:

func maxConsecutiveAnswers(answerKey string, k int) int {
	f := func(c byte) int {
		l, cnt := 0, 0
		for r, ch := range answerKey {
			if byte(ch) != c {
				cnt++
			}
			for cnt > k {
				if answerKey[l] != c {
					cnt--
				}
				l++
			}
		}
		return len(answerKey) - l
	}
	return max(f('T'), f('F'))
}
 
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

TypeScript:

function maxConsecutiveAnswers(answerKey: string, k: number): number {
    const f = (c: string): number => {
        let l = 0, cnt = 0;
        for (let r = 0; r < answerKey.length; r++) {
            if (answerKey[r] !== c) cnt++;
            while (cnt > k) {
                if (answerKey[l++] !== c) cnt--;
            }
        }
        return answerKey.length - l;
    };
    return Math.max(f('T'), f('F'));
}

Rust:

impl Solution {
    pub fn max_consecutive_answers(answer_key: String, k: i32) -> i32 {
        let n = answer_key.len();
        let k = k as usize;
        let chars: Vec<char> = answer_key.chars().collect();
        
        let f = |c: char| -> usize {
            let mut l = 0;
            let mut cnt = 0;
            for r in 0..n {
                if chars[r] != c {
                    cnt += 1;
                }
                while cnt > k {
                    if chars[l] != c {
                        cnt -= 1;
                    }
                    l += 1;
                }
            }
            n - l
        };
 
        std::cmp::max(f('T'), f('F')) as i32
    }
}

These code examples demonstrate the efficient sliding window solution for the problem, achieving optimal time complexity. The choice of language affects only the syntax, not the core algorithm.