If the number of T is not double of M, then "NO". If the first or last character is M, then "NO".

I made two arrays that had the count of T's from the right and from the left. Then I traversed the string and for every M, I checked if the number of T's on left and right are positive or not. (To achieve this I had another variable which had the count of 'M' processed)

` vector right(n), left(n); left[0] = 1; right[n — 1] = 1; for (int i = 1; i < n; i++) { if (s[i] == 'T') left[i] = left[i — 1] + 1; else left[i] = left[i — 1]; }

for (int i = n - 2; i >= 0; i--)
    {
        if (s[i] == 'T')
            right[i] = right[i + 1] + 1;
        else
            right[i] = right[i + 1];
    }

    int mp = 0;


    for (int i = 0; i < n; i++)
    {
        if (s[i] == 'M')
        {
            int l = left[i] - mp;
            int r = right[i] - mp;

            if (l > 0 && r > 0)
            {
                mp++;
            }
            else
            {
                cout << "NO\n";
                f = true;
                break;
            }
        }
    }`