Maximize the Confusion of an Exam — Problem & Solution
Maximize the Confusion of an Exam solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Maximize the Confusion of an Exam is a medium coding problem on strings, binary search and prefix sum, asked in Amazon, Google, Adobe and Arcesium interviews.
- Difficulty: Medium
- Topics: Strings, Binary Search, Prefix Sum, Sliding Window
- Asked at: Amazon, Google, Adobe, Arcesium
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
answerKey[i] is the answer to question i, either 'T' or 'F'. You may change the answer to any question, at most k times.
Return the maximum number of consecutive 'T's or consecutive 'F's you can produce.
Example 1
Input: answerKey = "TTFF", k = 2
Output: 4
Explanation: Flip both F to T.
Example 2
Input: answerKey = "TFFT", k = 1
Output: 3
Explanation: Flipping the first T gives "FFFT".
Example 3
Input: answerKey = "TTFTTFTT", k = 1
Output: 5
Constraints
1 <= answerKey.length <= 50000answerKey[i] is 'T' or 'F'1 <= k <= answerKey.length
Hints for Maximize the Confusion of an Exam
Hint 1
Solve it twice: once aiming for all
'T', once for all'F', and take the better.Hint 2
For a fixed target, a window is valid when it holds at most
kcharacters that are not the target.Hint 3
That predicate is monotone in the window's left edge, so one pass per target suffices.
How to solve Maximize the Confusion of an Exam
Decide the target character first. Then the problem becomes the familiar 'longest window with at most k mismatches' — grow on the right, shrink on the left whenever the mismatch count exceeds k. Run it for both targets.
Approach
- For a target
c, slide a window keepingbad, the count of characters that are notc. - While
bad > k, advance the left edge, decrementingbadwhen the character leaving was a mismatch. - Record the longest valid window, then repeat for the other target and take the maximum.
Why it works
Every final run is entirely 'T' or entirely 'F', so splitting into two independent passes loses nothing. Within a pass, removing a character can only lower the mismatch count, which makes the valid left edges a suffix and keeps the scan linear.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Solving for only one target misses the case where the other letter dominates.
- The two passes can share a window only with care — the mismatch counts are different.
kcan exceed the number of mismatches, in which case the whole string is the answer.
Reference solution
Python
def maxConsecutiveAnswers(answerKey: str, k: int) -> int:
def run(target: str) -> int:
l = 0
bad = 0
best = 0
for r, ch in enumerate(answerKey):
if ch != target:
bad += 1
while bad > k:
if answerKey[l] != target:
bad -= 1
l += 1
best = max(best, r - l + 1)
return best
return max(run("T"), run("F"))Java
private static int runConfusion(String answerKey, int k, char target) {
int l = 0, bad = 0, best = 0;
for (int r = 0; r < answerKey.length(); r++) {
if (answerKey.charAt(r) != target) bad++;
while (bad > k) {
if (answerKey.charAt(l) != target) bad--;
l++;
}
best = Math.max(best, r - l + 1);
}
return best;
}
public static int maxConsecutiveAnswers(String answerKey, int k) {
return Math.max(runConfusion(answerKey, k, 'T'), runConfusion(answerKey, k, 'F'));
}C++
static int runConfusion(const string& answerKey, int k, char target) {
int l = 0, bad = 0, best = 0;
for (int r = 0; r < (int) answerKey.size(); r++) {
if (answerKey[r] != target) bad++;
while (bad > k) {
if (answerKey[l] != target) bad--;
l++;
}
best = max(best, r - l + 1);
}
return best;
}
int maxConsecutiveAnswers(string answerKey, int k) {
return max(runConfusion(answerKey, k, 'T'), runConfusion(answerKey, k, 'F'));
}JavaScript
var maxConsecutiveAnswers = function(answerKey, k) {
var run = function(target) {
var l = 0, bad = 0, best = 0;
for (var r = 0; r < answerKey.length; r++) {
if (answerKey.charAt(r) !== target) bad++;
while (bad > k) {
if (answerKey.charAt(l) !== target) bad--;
l++;
}
if (r - l + 1 > best) best = r - l + 1;
}
return best;
};
return Math.max(run("T"), run("F"));
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Binary Search