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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximize the Confusion of an Exam

Number: 2134

Difficulty: Medium

Paid? No

Companies: Google, Amazon, Arcesium

Problem Description

A teacher is writing a test with n true/false questions. The teacher wants to maximize the number of consecutive questions with the same answer to confuse the students. You are given a string answerKey, where answerKey[i] represents the original answer for question i, and an integer k which is the maximum number of changes you can perform (changing any answer to 'T' or 'F'). The task is to return the maximum number of consecutive 'T's or 'F's obtainable after performing at most k operations.

Key Insights

  • The problem uses a sliding window to find the longest subarray where we can flip at most k characters.
  • You calculate the maximum window length for both target characters 'T' and 'F' separately.
  • Within the window, count the number of flips (i.e., the characters that are not the target).
  • If the flip count exceeds k, slide the window from the left until the count is at most k.
  • The answer is the maximum length among the two computed values.

Space and Time Complexity

Time Complexity: O(n) – We traverse the string possibly twice (once per target character). Space Complexity: O(1) – Only constant extra space is used.

Solution

We solve the problem using a sliding window approach. Two helper functions (or one function called twice) evaluate the maximum consecutive sequence for target characters 'T' and 'F'. For each target, expand the window by moving the right pointer and count flips (non-target characters). When the count exceeds k, move the left pointer to shrink the window until the count is within the limit. The maximum window size found is the answer. Finally, return the maximum from evaluating both targets.

Code Solutions

def maxConsecutiveAnswers(answerKey: str, k: int) -> int:
    # Helper function to compute maximum consecutive answers for a given target
    def maxConsecutive(target: str) -> int:
        max_length = 0
        left = 0
        count = 0  # Count of flips required (non-target characters)
        for right in range(len(answerKey)):
            if answerKey[right] != target:
                count += 1  # Increase flip count if character does not match target
            # If the flips exceed k, shrink the window from the left
            while count > k:
                if answerKey[left] != target:
                    count -= 1  # Reduce flip count as we exclude a non-target character
                left += 1  # Move the left pointer forward
            max_length = max(max_length, right - left + 1)  # Update maximum length
        return max_length

    # Check maximum consecutive length for both 'T' and 'F'
    return max(maxConsecutive('T'), maxConsecutive('F'))
← Back to All Questions