Maximize the Confusion of an Exam

medium string binary search sliding window prefix sum

Problem

Given a string answerKey of only 'T' and 'F' and an integer k, return the maximum number of consecutive equal answers achievable after changing at most k characters.

InputanswerKey = "TTFTTFTT", k = 1

Output5

Flip one F to get 5 consecutive Ts.

answerKey (T/F)

def max_consecutive_answers(answer_key, k):
    l = 0
    cnt = {'T': 0, 'F': 0}
    best = 0
    for r, ch in enumerate(answer_key):
        cnt[ch] += 1
        while min(cnt['T'], cnt['F']) > k:
            cnt[answer_key[l]] -= 1
            l += 1
        best = max(best, r - l + 1)
    return best

function maxConsecutiveAnswers(answerKey, k) {
  let l = 0, best = 0;
  const cnt = { T: 0, F: 0 };
  for (let r = 0; r < answerKey.length; r++) {
    cnt[answerKey[r]]++;
    while (Math.min(cnt.T, cnt.F) > k) {
      cnt[answerKey[l]]--;
      l++;
    }
    best = Math.max(best, r - l + 1);
  }
  return best;
}

class Solution {
    public int maxConsecutiveAnswers(String answerKey, int k) {
        int l = 0, best = 0, t = 0, f = 0;
        for (int r = 0; r < answerKey.length(); r++) {
            if (answerKey.charAt(r) == 'T') t++; else f++;
            while (Math.min(t, f) > k) {
                if (answerKey.charAt(l) == 'T') t--; else f--;
                l++;
            }
            best = Math.max(best, r - l + 1);
        }
        return best;
    }
}

int maxConsecutiveAnswers(string answerKey, int k) {
    int l = 0, best = 0, t = 0, f = 0;
    for (int r = 0; r < (int)answerKey.size(); r++) {
        if (answerKey[r] == 'T') t++; else f++;
        while (min(t, f) > k) {
            if (answerKey[l] == 'T') t--; else f--;
            l++;
        }
        best = max(best, r - l + 1);
    }
    return best;
}

Explanation

We want the longest run of identical answers after flipping at most k characters. A window can become all the same letter cheaply if the less common letter inside it appears few enough times — those are exactly the ones we'd flip.

So we slide a window and keep counts of both T and F. The number of flips a window needs is min(cnt['T'], cnt['F']), the count of whichever letter is in the minority.

As the right pointer adds characters, if that minimum exceeds k the window can't be unified within budget, so we move the left pointer forward, lowering the leaving letter's count, until it's valid again. Then we record best as r - l + 1.

Example: answerKey = "TTFTTFTT", k = 1. A window like "TTFTT" has 4 T's and 1 F, so min = 1 ≤ k — flip that single F to get 5 equal answers, the answer.

This one window handles both "make everything T" and "make everything F" at the same time, and runs in linear time with constant space.

Time: O(n) Space: O(1)