Maximize the Confusion of an Exam

Approach

The base condition occurs when ‘K’ is greater than half of the string length. We can argue that we can make the entire string either true or false. Now we calculate the number of consecutive T’s and the number of consecutive F’s using two separate function calls. Then we greedily try to find an answer such that the given two conditions are established. Finally, we return the answer.

Algorithm

1. If ‘K’ is higher than half the length of the string, the answer is the string length. Since if the count of 'F' is greater than or equal to the count of 'T,' then the count of 'T' must be less than or equal to the count of 'F,' and vice versa.
2. We've now called our function consecutiveCount() twice. We try to determine the maximum number of consecutive T's in the first call. Then, we try to determine the maximum number of consecutive Fs in the second call. The ‘BEGIN’ variable in the consecutiveCount() function represents the starting index from which a subsequent string begins.
3.  Now, we create a loop in which two conditions are established if character c is not equal to the string element.
4.  If ‘COUNT’ equals ‘K’, the ‘BEGIN’ variable is updated, which indicates the first modified character of the string is removed, and the current character is modified.
5.  If ‘M’ does not equal ‘K’, change the current character and increment ‘M.’Also, for each iteration, update ‘ANS’. Finally, return ‘ANS’.

Program

#include<iostream>
#include<string>
#include<vector>

using namespace std;

int consecutiveCount(string str, int k, char c) {
  int ans = 0, begin = 0, n = str.size();

  // Stores index of modified characters in the string.
  vector <int> v(n);

  // Index of first character to be modified.
  int first = 0;

  // Index of last character to be modified.
  int last = 0;

  // Number of characters modified.
  int count = 0;
  for (int i = 0; i < n; i++) {
    if (str[i] != c) {
      // If count == k, we store update begin and modify the current character.
      if (k == count) {
        begin = v[first++] + 1;
        v[last++] = i;
      }

      // We modify the current character and increment count.
      else {
        v[last++] = i;
        count++;
      }
    }
    ans = max(ans, i - begin + 1);
  }
  return ans;
}

int maximizeConfusionOfAnExam(string answerKey, int k) {
  int ans1 = consecutiveCount(answerKey, k, 'T');
  int ans2 = consecutiveCount(answerKey, k, 'F');
  return max(ans1, ans2);
}

int main() {
  string answerKey;
  cout << "Enter the answer key: ";
  cin >> answerKey;
  cout << "Enter the value of K: ";
  int K;
  cin >> K;
  cout << "Answer is: " << maximizeConfusionOfAnExam(answerKey, K);
  return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Input

Enter the answer key: TTFTTFTT 
Enter the value of K: 1

Output

Answer is: 5

Time Complexity

O(N), where ‘N’ is the size of the string.

We are using one for loop in the consecutiveCount method. The loop iterates upon string length. Thus the time complexity is O(N).

Space Complexity

O(1). We are using constant space as we just declaring a few variables. Thus space complexity is O(1).

Key Takeaways

We saw an interesting ad-hoc problem i.e., Maximize the confusion of an Exam. It took O(N) time and constant space. But every ad-hoc problem is unique in itself and requires separate logic, thus don’t stop practising and Move to our industry-leading practice platform Coding Ninjas Studio to practice more such problems and many more.

Thank You and Happy Coding!