Question 3 Protyay

#include <bits/stdc++.h>
using namespace std;

long getMaximumPrizes(string inputString) {
    long countA = 0, countAM = 0, countAMZ = 0;
    long maxPrizes = 0;

    // Traverse the string to count "A", "AM", and "AMZ" subsequences
    for (char c : inputString) {
        if (c == 'Z') {
            countAMZ += countAM;  // Every "AM" can form an "AMZ" when followed by "Z"
        }
        if (c == 'M') {
            countAM += countA;  // Every "A" can form an "AM" when followed by "M"
        }
        if (c == 'A') {
            countA++;  // Count of "A"s found
        }
    }

    // Initially, the count of "AMZ" subsequences without adding any letter
    maxPrizes = countAMZ;

    // Try adding each letter ('A', 'M', 'Z') and calculate the maximum result
    // Add 'A' - This will start new "AMZ" subsequences from "AMZ" found earlier
    maxPrizes = max(maxPrizes, countAMZ + countA);

    // Add 'M' - This will complete "A"s into "AM" subsequences
    maxPrizes = max(maxPrizes, countAMZ + countA);

    // Add 'Z' - This will complete "AM"s into "AMZ" subsequences
    maxPrizes = max(maxPrizes, countAMZ + countAM);

    return maxPrizes;
}

// int main() {
//     // Sample Test Cases
//     string inputString = "AKMMZ";
//     cout << getMaximumPrizes(inputString) << endl;  // Expected output: 4

//     string inputString2 = "AZ";
//     cout << getMaximumPrizes(inputString2) << endl;  // Expected output: 1

//     return 0;
// }