Maximize the Confusion of an Exam - Practice Coding Problems

Maximize the Confusion of an Exam - Problem

A teacher is writing a test with n true/false questions, with 'T' denoting true and 'F' denoting false. He wants to confuse the students by maximizing the number of consecutive questions with the same answer (multiple trues or multiple falses in a row).

You are given a string answerKey, where answerKey[i] is the original answer to the i^th question. In addition, you are given an integer k, the maximum number of times you may perform the following operation:

Change the answer key for any question to 'T' or 'F' (i.e., set answerKey[i] to 'T' or 'F').

Return the maximum number of consecutive 'T's or 'F's in the answer key after performing the operation at most k times.

Input & Output

Example 1 — Basic Case

$ Input: answerKey = "TTFF", k = 2

› Output: 4

💡 Note: We can change at most 2 characters. Change both F's to T's to get "TTTT" with length 4, or change both T's to F's to get "FFFF" with length 4.

Example 2 — Mixed Pattern

$ Input: answerKey = "TFFT", k = 1

› Output: 3

💡 Note: We can change 1 character. Change the middle F to T to get "TTFT" or "TFTT", giving us a maximum consecutive length of 3 T's.

Example 3 — No Changes Needed

$ Input: answerKey = "TTTTTTTT", k = 2

› Output: 8

💡 Note: All characters are already the same, so we don't need any changes. The entire string has length 8.

Constraints

1 ≤ answerKey.length ≤ 5 × 10⁴
answerKey[i] is either 'T' or 'F'
0 ≤ k ≤ answerKey.length

Visualization

Tap to expand

Understanding the Visualization

Input

String with T's and F's, plus change limit k

Process

Find longest substring by changing ≤ k characters

Output

Maximum length of consecutive same characters

Key Takeaway

🎯 Key Insight: Use sliding window to maintain at most k changes while maximizing consecutive characters

Asked in

F Facebook 35 a Amazon 28 G Google 22

The key insight is to use sliding window technique to find the longest substring where we can change at most k characters. Apply sliding window twice: once for maximizing T's and once for F's. Best approach is sliding window with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Substrings	O(n³)	O(1)	Check every possible substring and count changes needed to make it uniform
Sliding Window - Two Passes	O(n)	O(1)	Use sliding window technique to find longest substring for each character type

Brute Force - Check All Substrings — Algorithm Steps

For each starting position i
For each ending position j ≥ i
Count changes needed for all T's and all F's
If changes ≤ k, update maximum length

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Substrings

Check all possible start-end combinations

Count Changes

For each substring, count changes needed for all T's or F's

Find Maximum

Return length of longest valid substring

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int solution(char* answerKey, int k) {
    int n = strlen(answerKey);
    int maxLen = 0;
    
    // Check all possible substrings
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            // Count changes needed to make all T's
            int changesForT = 0;
            for (int idx = i; idx <= j; idx++) {
                if (answerKey[idx] != 'T') {
                    changesForT++;
                }
            }
            
            // Count changes needed to make all F's
            int changesForF = 0;
            for (int idx = i; idx <= j; idx++) {
                if (answerKey[idx] != 'F') {
                    changesForF++;
                }
            }
            
            // If we can make this substring uniform within k changes
            if (changesForT <= k || changesForF <= k) {
                int len = j - i + 1;
                if (len > maxLen) {
                    maxLen = len;
                }
            }
        }
    }
    
    return maxLen;
}

int main() {
    char answerKey[100001];
    int k;
    
    fgets(answerKey, sizeof(answerKey), stdin);
    answerKey[strcspn(answerKey, "\n")] = 0;
    
    scanf("%d", &k);
    
    int result = solution(answerKey, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Three nested loops: start position × end position × counting changes

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables to track maximum length and counts

✓ Linear Space

32.0K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Substrings — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler