https://codeforces.com/contest/1509/problem/B
시간 1초, 메모리 256MB

input :

• t (1 ≤ t ≤ 5000)
• n (3 ≤ n ≤ 105)
• a string of length n consisting of only the characters 'T' and 'M'.

output :

• For each test case, print a single line containing YES if the described partition exists, and a single line containing NO otherwise.
  명시된 분류를 할 수 있다면 "YES"를 그렇지 않은 경우엔 "NO"를 출력하시오.

조건 :

• 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.
  입력받은 문자열이 서로 독립된 부분 문자열로 구분이 가능한지 알아내고 싶다. 즉, 문자열을 이루는 하나의 문자는 한개의 부분문자열에 속해야 한다.

---

일단 M의 개수를 확인하자.

개수

언제나 구성하고 있는 문자열에 'M' n개, 'T' 2\*n개 여야 분류를 할 수 있을 것이다.

방법

어떤 방법으로 이후에 확인을 할 수 있을까?

처음에는 그냥 단순히 가장 먼 것을 붙여주면 되지 않을까? 했다.
그러나 이런 경우뿐 아니라 중간에 존재하는 'T'를 가져가야 부분문자열을 형성하는 경우도 존재한다.

각 'M'을 기준으로 번호를 붙여보자.
그리고 나면 'T'에도 번호를 붙일 수가 있다. 각 'M'에 대응되는 것들이 2개 존재하는데
인덱스 기준 : 'T' < 'M' < 'T'의 순서가 성립 되어야 부분문자열을 구성할 수 있다.

그러니까 각 M을 기준으로 비교하면서 찾도록 하자.

import sys

t = int(sys.stdin.readline())
for _ in range(t):
    n = int(sys.stdin.readline())
    data = sys.stdin.readline().rstrip()
    Ts = []
    Ms = []
    flag = 0

    for idx, item in enumerate(data):
        if item == 'M':
            Ms.append(idx)
        else:
            Ts.append(idx)

    if data[0] == 'M' or data[-1] == 'M' or len(Ms) * 3 != n:
        print("NO")
        continue

    for i in range(len(Ms)):
        if Ts[i] > Ms[i] or Ms[i] > Ts[i + len(Ms)]:
            flag = 1
            break

    print("NO" if flag else "YES")

그리고 'M'에 대응하는 놈들은 2개이니까 이것을 확인하기 위해 'M'의 개수만큼 뒤에 존재하는 T가 뒤에 오는 놈이라고 생각하면 된다.