TMT Document
Contest: Codeforces Round 715 (Div. 2)
Difficulty rating: 1100
Tags: greedy

The student council has a shared document file. Every day, some members of the student council write the sequence TMT (short for Towa Maji Tenshi) in it.

However, one day, the members somehow entered the sequence into the document at the same time, creating a jumbled mess. Therefore, it is Suguru Doujima's task to figure out whether the document has malfunctioned. Specifically, he is given a string of length $$$n$$$ whose characters are all either T or M, and he wants to figure out if it is possible to partition it into some number of disjoint subsequences, all of which are equal to TMT. That is, each character of the string should belong to exactly one of the subsequences.

A string $$$a$$$ is a subsequence of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero) characters.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \le t \le 5000$$$)  — the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$3 \le n < 10^5$$$), the number of characters in the string entered in the document. It is guaranteed that $$$n$$$ is divisible by $$$3$$$.

The second line of each test case contains a string of length $$$n$$$ consisting of only the characters T and M.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output format:
For each test case, print a single line containing YES if the described partition exists, and a single line containing NO otherwise.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the string itself is already a sequence equal to TMT.

In the third test case, we may partition the string into the subsequences TMTMTT. Both the bolded and the non-bolded subsequences are equal to TMT.

Example input:
5
3
TMT
3
MTT
6
TMTMTT
6
TMTTTT
6
TTMMTT

Example output:
YES
NO
YES
NO
YES

Editorial:
There are many slightly different solutions, all based on some sort of greedy idea. Write $$$n = 3k$$$ for convenience. Obviously, the string must have $$$k$$$ characters M and $$$2k$$$ characters T for the partition to be possible, so we can just discard all other cases.
Now, let's consider the first M character in the string. This must be part of some TMT subsequence, so we must choose a T character to its left to work as the first character of this subsequence. Which character should we choose? Well, it seems intuitive to match it with the first T character we find going from left to right - it is certainly not the right character of any sequence, and it seems like a good idea to assign it to the first M character since characters that are further to the right may be too far right to match with this character.
Continuing this idea, we come up with the following greedy algorithm: Take the first $$$k$$$ T characters and use them as the first characters of the subsequences, matching them with the $$$k$$$ M characters from left to right greedily. Similarly, take the last $$$k$$$ T characters and match them with each M character from left to right greedily. If either of these steps fails, the partition is impossible. This can be formalized into the following observation, which is both easy to prove and gives a solution that is very easy to implement.
Claim. Let $$$m_1 < m_2 < \dots < m_k$$$ be the positions of the M characters and let $$$t_1 < t_2 < \dots < t_{2k}$$$ be the positions of the T characters. Then the partition exists if and only if $$$t_i < m_i < t_{i + k}$$$ for $$$1 \le i \le k$$$.
Proof. If the condition holds then we can just choose the $$$k$$$ subsequences with indices $$$(t_i, m_i, t_{i + k})$$$, so it is sufficient. To see that it's necessary, consider the first $$$i$$$ M characters with indices $$$m_1, m_2, \dots, m_i$$$, and consider the left T characters in the subsequence they're in. These are to the left of their corresponding M characters, and in particular they are to the left of the $$$i$$$-th M character. Thus there's at least $$$i$$$ T characters to the left of the $$$i$$$-th M character, meaning $$$t_i < m_i$$$. The other inequality is proved similarly.