We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximize the Confusion of an Exam

Difficulty: Medium

Problem Description

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 ith question. In addition, you are given an integer k, the maximum number of times you may change the answer 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.

Key Insights

  • The goal is to find the longest substring of 'T's or 'F's after making at most k changes.
  • A sliding window approach can be utilized to maintain a window of characters while counting the number of changes needed.
  • The window expands until the number of changes exceeds k, then it contracts from the left to maintain the constraint.
  • The maximum length of the valid window is the answer.

Space and Time Complexity

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

Solution

The problem can be solved using the sliding window technique. We maintain two pointers, left and right, representing the current window in the string. As we expand the right pointer to include more characters, we count how many characters need to be changed to make the entire window either all 'T's or all 'F's. If the number of changes exceeds k, we shrink the window from the left by moving the left pointer until we are back within the allowed number of changes. Throughout this process, we keep track of the maximum length of valid windows found.

Code Solutions

def maxConsecutiveAnswers(answerKey: str, k: int) -> int:
    left = 0
    max_length = 0
    count_T = 0
    count_F = 0
    
    for right in range(len(answerKey)):
        if answerKey[right] == 'T':
            count_T += 1
        else:
            count_F += 1
            
        # If we exceed k changes, shrink the window
        while min(count_T, count_F) > k:
            if answerKey[left] == 'T':
                count_T -= 1
            else:
                count_F -= 1
            left += 1
        
        # Update the maximum length of the window
        max_length = max(max_length, right - left + 1)
    
    return max_length
← Back to All Questions