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:

1
2
3
4
5
6


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:

1
2
3
4
5
6
7


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:

1
2
3
4
5
6
7


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. 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

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

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


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;
	}
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


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;
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


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'))
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


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'))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


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')
		)
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


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

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

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


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;
	}
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


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;
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


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
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


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
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


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).

Problem#

Examples#

Solution#

Method 1 - Two Sliding Windows#

Intuition#

Approach#

Code#

Complexity#

Method 2 - One Pass Sliding Window with Frequency Map#

Intuition#

Approach#

Code#

Complexity#

Problem

Examples

Solution

Method 1 - Two Sliding Windows

Intuition

Approach

Code

Complexity

Method 2 - One Pass Sliding Window with Frequency Map

Intuition

Approach

Code

Complexity