Maximize the Confusion of an Exam — Medium Problem & Solution

answerKey[i] is the answer to question i, either 'T' or 'F'. You may change the answer to any question, at most k times.

Difficulty: Medium
Topics: Strings, Binary Search, Sliding Window, Prefix Sum
Asked at: Amazon, Google, Adobe
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 <= 50000
answerKey[i] is 'T' or 'F'
1 <= k <= answerKey.length

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 keeping bad, the count of characters that are not c.
While bad > k, advance the left edge, decrementing bad when 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.
k can 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"))

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue