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<int> 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;
}
}
}`
The two arrays to count from left and right are a good start!
"If the first or last character is M, then "NO"."
That is one special case. Take a look at "TMMTTT". This cannot work. Why? The first M is ok. we got 1 T on the left of it. The second M is not okay, since we only have one T two the left! You cannot provide for all M!
Can you generalize this?
this is handled by the right and left array, when we will come to the second M, the left value will be 0, and "NO" will be printed
I see, you are right! though, you are iterating from left to right but checking both directions. What does your Algorithm do with "TMTTMT"? It will fail at the second M, since there is only 1 T to the right and 2>1. But "TMTTMT" can be split into "TMT" and "TMT"!