Maximize the Confusion of an Exam

Medium
792.

Maximize the Confusion of an Exam

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.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} answerKey
 * @param {number} k
 * @return {number}
 */
var maxConsecutiveAnswers = function(answerKey, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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

Hints for Maximize the Confusion of an Exam

  1. Hint 1

    Solve it twice: once aiming for all 'T', once for all 'F', and take the better.

  2. Hint 2

    For a fixed target, a window is valid when it holds at most k characters that are not the target.

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

  1. For a target c, slide a window keeping bad, the count of characters that are not c.
  2. While bad > k, advance the left edge, decrementing bad when the character leaving was a mismatch.
  3. 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"))

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