Maximize the Confusion of an Exam

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.

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.

Solution

Method 1 - Two Sliding Windows

This problem is similar to [Longest Subarray with Ones after Replacement](longest-subarray-with-ones-after-replacement). Since the string contains only 'T' and 'F', we can use a sliding window to find the longest substring where we can flip at most k of either character to make all characters the same. We do this for both 'T' and 'F' and take the maximum.

Intuition

We want the longest substring of all 'T's or all 'F's after at most k flips. For each character ('T' and 'F'), use a sliding window to keep at most k of that character in the window. If the count exceeds k, move the left pointer forward until the window is valid again. The answer is the maximum window size found for both cases.

Approach

1. For both 'T' and 'F', use a helper function to find the longest substring where at most k of the chosen character are flipped.
2. Use two pointers to maintain the window and a counter for the number of flips used.
3. Expand the window to the right, and if the number of flips exceeds k, move the left pointer forward and update the counter.
4. Track the maximum window size for both cases and return the maximum.

Code

C++

class Solution {
public:
	int maxConsecutiveAnswers(string answerKey, int k) {
		return max(solve(answerKey, k, 'T'), solve(answerKey, k, 'F'));
	}
	int solve(const string& s, int k, char ch) {
		int l = 0, cnt = 0, res = 0;
		for (int r = 0; r < s.size(); ++r) {
			if (s[r] == ch) ++cnt;
			while (cnt > k) {
				if (s[l++] == ch) --cnt;
			}
			res = max(res, r - l + 1);
		}
		return res;
	}
};

Go

func maxConsecutiveAnswers(answerKey string, k int) int {
	return max(solve(answerKey, k, 'T'), solve(answerKey, k, 'F'))
}

func solve(s string, k int, ch byte) int {
	l, cnt, res := 0, 0, 0
	for r := 0; r < len(s); r++ {
		if s[r] == ch {
			cnt++
		}
		for cnt > k {
			if s[l] == ch {
				cnt--
			}
			l++
		}
		if r-l+1 > res {
			res = r - l + 1
		}
	}
	return res
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

Java

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

Kotlin

class Solution {
	fun maxConsecutiveAnswers(answerKey: String, k: Int): Int {
		fun solve(s: String, k: Int, ch: Char): Int {
			var l = 0
			var cnt = 0
			var res = 0
			for (r in s.indices) {
				if (s[r] == ch) cnt++
				while (cnt > k) {
					if (s[l++] == ch) cnt--
				}
				res = maxOf(res, r - l + 1)
			}
			return res
		}
		return maxOf(solve(answerKey, k, 'T'), solve(answerKey, k, 'F'))
	}
}

Python

class Solution:
	def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:
		def solve(s: str, k: int, ch: str) -> int:
			l = cnt = res = 0
			for r, c in enumerate(s):
				if c == ch:
					cnt += 1
				while cnt > k:
					if s[l] == ch:
						cnt -= 1
					l += 1
				res = max(res, r - l + 1)
			return res
		return max(solve(answerKey, k, 'T'), solve(answerKey, k, 'F'))

Rust

impl Solution {
	pub fn max_consecutive_answers(answer_key: String, k: i32) -> i32 {
		fn solve(s: &str, k: i32, ch: char) -> i32 {
			let (mut l, mut cnt, mut res) = (0, 0, 0);
			let s: Vec<char> = s.chars().collect();
			for r in 0..s.len() {
				if s[r] == ch { cnt += 1; }
				while cnt > k {
					if s[l] == ch { cnt -= 1; }
					l += 1;
				}
				res = res.max((r - l + 1) as i32);
			}
			res
		}
		std::cmp::max(
			solve(&answer_key, k, 'T'),
			solve(&answer_key, k, 'F')
		)
	}
}

TypeScript

class Solution {
	maxConsecutiveAnswers(answerKey: string, k: number): number {
		function solve(s: string, k: number, ch: string): number {
			let l = 0, cnt = 0, res = 0;
			for (let r = 0; r < s.length; r++) {
				if (s[r] === ch) cnt++;
				while (cnt > k) {
					if (s[l++] === ch) cnt--;
				}
				res = Math.max(res, r - l + 1);
			}
			return res;
		}
		return Math.max(solve(answerKey, k, 'T'), solve(answerKey, k, 'F'));
	}
}

Complexity

• ⏰ Time complexity: O(n), since each character is visited at most twice for each case.
• 🧺 Space complexity: O(1), only a few variables are used.

Method 2 - One Pass Sliding Window with Frequency Map

Intuition

Instead of running two separate sliding windows, we can use a frequency map to track the count of each character ('T' and 'F') in the current window. The window is valid as long as the number of replacements needed (window size minus the count of the most frequent character) does not exceed k. This allows us to find the longest valid window in a single pass.

Approach

1. Use a frequency map to count occurrences of 'T' and 'F' in the current window.
2. Track the maximum frequency of any character in the window.
3. Expand the window to the right. If the number of replacements needed (window size - maxFreq) exceeds k, shrink the window from the left.
4. The answer is the largest window size found.

Code

C++

class Solution {
public:
	int maxConsecutiveAnswers(string answerKey, int k) {
		int maxFreq = 0, l = 0;
		unordered_map<char, int> count;
		for (int r = 0; r < answerKey.size(); ++r) {
			count[answerKey[r]]++;
			maxFreq = max(maxFreq, count[answerKey[r]]);
			if (r - l + 1 > maxFreq + k) {
				count[answerKey[l]]--;
				l++;
			}
		}
		return answerKey.size() - l;
	}
};

Go

func maxConsecutiveAnswers(answerKey string, k int) int {
	count := map[byte]int{'T': 0, 'F': 0}
	maxFreq, l := 0, 0
	for r := 0; r < len(answerKey); r++ {
		count[answerKey[r]]++
		if count[answerKey[r]] > maxFreq {
			maxFreq = count[answerKey[r]]
		}
		if r-l+1 > maxFreq+k {
			count[answerKey[l]]--
			l++
		}
	}
	return len(answerKey) - l
}

Java

class Solution {
	public int maxConsecutiveAnswers(String answerKey, int k) {
		int maxFreq = 0, i = 0;
		Map<Character, Integer> charCount = new HashMap<>();
		for (int j = 0; j < answerKey.length(); j++) {
			char c = answerKey.charAt(j);
			charCount.put(c, charCount.getOrDefault(c, 0) + 1);
			maxFreq = Math.max(maxFreq, charCount.get(c));
			if (j - i + 1 > maxFreq + k) {
				char leftChar = answerKey.charAt(i);
				charCount.put(leftChar, charCount.get(leftChar) - 1);
				i++;
			}
		}
		return answerKey.length() - i;
	}
}

Kotlin

class Solution {
	fun maxConsecutiveAnswers(answerKey: String, k: Int): Int {
		val charCount = mutableMapOf<Char, Int>()
		var maxFreq = 0
		var i = 0
		for (j in answerKey.indices) {
			val c = answerKey[j]
			charCount[c] = (charCount[c] ?: 0) + 1
			maxFreq = maxOf(maxFreq, charCount[c]!!)
			if (j - i + 1 > maxFreq + k) {
				val leftChar = answerKey[i]
				charCount[leftChar] = charCount[leftChar]!! - 1
				i++
			}
		}
		return answerKey.length - i
	}
}

Python

class Solution:
	def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:
		from collections import defaultdict
		char_count = defaultdict(int)
		max_freq = i = 0
		for j, c in enumerate(answerKey):
			char_count[c] += 1
			max_freq = max(max_freq, char_count[c])
			if j - i + 1 > max_freq + k:
				char_count[answerKey[i]] -= 1
				i += 1
		return len(answerKey) - i

Rust

use std::collections::HashMap;
impl Solution {
	pub fn max_consecutive_answers(answer_key: String, k: i32) -> i32 {
		let mut count = HashMap::new();
		let (mut max_freq, mut l) = (0, 0);
		let s = answer_key.as_bytes();
		for r in 0..s.len() {
			let c = s[r];
			*count.entry(c).or_insert(0) += 1;
			max_freq = max_freq.max(*count.get(&c).unwrap());
			if (r as i32 - l as i32 + 1) > max_freq + k {
				let left_c = s[l];
				*count.get_mut(&left_c).unwrap() -= 1;
				l += 1;
			}
		}
		(s.len() - l) as i32
	}
}

TypeScript

class Solution {
	maxConsecutiveAnswers(answerKey: string, k: number): number {
		const charCount: Record<string, number> = {};
		let maxFreq = 0, i = 0;
		for (let j = 0; j < answerKey.length; j++) {
			const c = answerKey[j];
			charCount[c] = (charCount[c] || 0) + 1;
			maxFreq = Math.max(maxFreq, charCount[c]);
			if (j - i + 1 > maxFreq + k) {
				const leftChar = answerKey[i];
				charCount[leftChar]--;
				i++;
			}
		}
		return answerKey.length - i;
	}
}

Complexity

• ⏰ Time complexity: O(n), since each character is visited at most twice.
• 🧺 Space complexity: O(1) (since only two characters are tracked).