What is the brute force approach and complexity for Maximize the Confusion of an Exam?

For each start, grow right while min(T count, F count) ≤ k with time complexity O(N²) and space complexity O(1).

What is the optimal approach and complexity for Maximize the Confusion of an Exam?

Longest window with ≤ k F's, longest window with ≤ k T's, take the max with optimal time complexity O(N) and space complexity O(1).

How do you identify the pattern for Maximize the Confusion of an Exam?

Look for key signals in the prompt: "maximum number of consecutive" indicates Longest contiguous range → variable window.; "change at most k answers" indicates A budget of k "bad" positions inside the window.; "only 'T' or 'F'" indicates Just two letters → fix the target and count only the other letter, no 26-array needed..

Maximize the Confusion of an Exam

Medium·LeetCode #2024 Pro OnlyMedium

LeetCode

Problem Statement

A teacher has written the answer key for a true/false test as a string answerKey, where each character is 'T' (true) or 'F' (false).

The teacher wants to confuse the students by making the longest possible run of identical answers in a row (all 'T' or all 'F').

The teacher may change at most k answers (turn a 'T' into an 'F' or the other way round).

Return the length of the longest run of the same answer the teacher can make.

Input

A string answerKey made of 'T' and 'F', and an integer k.

Output

One integer: the longest block of identical answers possible after at most k changes.

Example 1

Input: answerKey = "TTFF", k = 2

Output: 4

Change both F's to T (or both T's to F). The whole key is one letter.

Example 2

Input: answerKey = "TFFT", k = 1

Output: 3

Change the first T to F to get "FFFT", or the last T to get "TFFF". Either way the run has length 3.

Example 3

Input: answerKey = "TTFTTFTT", k = 1

Output: 5

Change the first F to get "TTTTTFTT" (run of 5), or the second F to get "TTFTTTTT" (also 5).

Constraints

• 1 ≤ answerKey.length ≤ 5 · 10^4
• answerKey[i] is 'T' or 'F'
• 1 ≤ k ≤ answerKey.length

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“maximum number of consecutive”

→ Longest contiguous range → variable window.

“change at most k answers”

→ A budget of k "bad" positions inside the window.

“only 'T' or 'F'”

→ Just two letters → fix the target and count only the other letter, no 26-array needed.

Approach Complexity Ladder

Brute Force — every start, grow while fixableO(N²)O(1)

For each start, grow right while min(T count, F count) ≤ k

Optimal — two sliding-window passes (all T, then all F)O(N)O(1)

Longest window with ≤ k F's, longest window with ≤ k T's, take the max

Brute Force Intuition

Try every start. Grow the end while counting T's and F's. To make the block all one letter, change the smaller group, which costs min(countT, countF). While that is ≤ k, the block is a candidate. When it goes above k, stop for this start.

Recognition rule for this sub-pattern:

Validity depends on the counts of things inside the window (distinct types, most frequent char, required letters). Keep a count map that updates on every add/remove.

Remember this · Sliding Window

Trigger

Contiguous subarray / substring + longest, shortest, maximum, count, or "of size K".

Think

Can I keep a valid range and move it, instead of checking every subarray from scratch?

Key question

When is my current window valid?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Sliding Window translate into production architectures and low-level memory mechanics.

LLD Machine Coding

Sliding Window Rate Limiter

Implementing token bucket and sliding log request throttlers in real backend services.

Explore Track

C++ Internals

Stack vs Heap, Placement new & Layout

Cache line locality when traversing contiguous windows in memory.

Explore Track

Longest Repeating Character Replacement Length of Longest Subarray With at Most K Frequency