Linguistics (Codeforces 1685B)
Tags: Greedy, strings

Alina has discovered a weird language, which contains only $$$4$$$ words: $$$\texttt{A}$$$, $$$\texttt{B}$$$, $$$\texttt{AB}$$$, $$$\texttt{BA}$$$. It also turned out that there are no spaces in this language: a sentence is written by just concatenating its words into a single string.Alina has found one such sentence $$$s$$$ and she is curious: is it possible that it consists of precisely $$$a$$$ words $$$\texttt{A}$$$, $$$b$$$ words $$$\texttt{B}$$$, $$$c$$$ words $$$\texttt{AB}$$$, and $$$d$$$ words $$$\texttt{BA}$$$?In other words, determine, if it's possible to concatenate these $$$a+b+c+d$$$ words in some order so that the resulting string is $$$s$$$. Each of the $$$a+b+c+d$$$ words must be used exactly once in the concatenation, but you can choose the order in which they are concatenated.

Input: The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases. The description of the test cases follows.The first line of each test case contains four integers $$$a$$$, $$$b$$$, $$$c$$$, $$$d$$$ ($$$0\le a,b,c,d\le 2\cdot 10^5$$$) — the number of times that words $$$\texttt{A}$$$, $$$\texttt{B}$$$, $$$\texttt{AB}$$$, $$$\texttt{BA}$$$ respectively must be used in the sentence.The second line contains the string $$$s$$$ ($$$s$$$ consists only of the characters $$$\texttt{A}$$$ and $$$\texttt{B}$$$, $$$1\le |s| \le 2\cdot 10^5$$$, $$$|s|=a+b+2c+2d$$$)  — the sentence. Notice that the condition $$$|s|=a+b+2c+2d$$$ (here $$$|s|$$$ denotes the length of the string $$$s$$$) is equivalent to the fact that $$$s$$$ is as long as the concatenation of the $$$a+b+c+d$$$ words.The sum of the lengths of $$$s$$$ over all test cases doesn't exceed $$$2\cdot 10^5$$$.

Output: For each test case output $$$\texttt{YES}$$$ if it is possible that the sentence $$$s$$$ consists of precisely $$$a$$$ words $$$\texttt{A}$$$, $$$b$$$ words $$$\texttt{B}$$$, $$$c$$$ words $$$\texttt{AB}$$$, and $$$d$$$ words $$$\texttt{BA}$$$, and $$$\texttt{NO}$$$ otherwise. You can output each letter in any case.

Note: In the first test case, the sentence $$$s$$$ is $$$\texttt{B}$$$. Clearly, it can't consist of a single word $$$\texttt{A}$$$, so the answer is $$$\texttt{NO}$$$.In the second test case, the sentence $$$s$$$ is $$$\texttt{AB}$$$, and it's possible that it consists of a single word $$$\texttt{AB}$$$, so the answer is $$$\texttt{YES}$$$.In the third test case, the sentence $$$s$$$ is $$$\texttt{ABAB}$$$, and it's possible that it consists of one word $$$\texttt{A}$$$, one word $$$\texttt{B}$$$, and one word $$$\texttt{BA}$$$, as $$$\texttt{A} + \texttt{BA} + \texttt{B} = \texttt{ABAB}$$$.In the fourth test case, the sentence $$$s$$$ is $$$\texttt{ABAAB}$$$, and it's possible that it consists of one word $$$\texttt{A}$$$, one word $$$\texttt{AB}$$$, and one word $$$\texttt{BA}$$$, as $$$\texttt{A} + \texttt{BA} + \texttt{AB} = \texttt{ABAAB}$$$. In the fifth test case, the sentence $$$s$$$ is $$$\texttt{BAABBABBAA}$$$, and it's possible that it consists of one word $$$\texttt{A}$$$, one word $$$\texttt{B}$$$, two words $$$\texttt{AB}$$$, and two words $$$\texttt{BA}$$$, as $$$\texttt{BA} + \texttt{AB} + \texttt{B} + \texttt{AB} + \texttt{BA} + \texttt{A}= \texttt{BAABBABBAA}$$$.

Sample Inputs:
8
1 0 0 0
B
0 0 1 0
AB
1 1 0 1
ABAB
1 0 1 1
ABAAB
1 1 2 2
BAABBABBAA
1 1 2 3
ABABABBAABAB
2 3 5 4
AABAABBABAAABABBABBBABB
1 3 3 10
BBABABABABBBABABABABABABAABABA

Sample Outputs:
NO
YES
YES
YES
YES
YES
NO
YES

Solution (Python):
import sys

def solve():
    inp = sys.stdin.readline
    (a, b, c, d) = map(int, inp().split())
    s = inp()
    if s.count('A') != a + c + d or s.count('B') != b + c + d:
        print('NO')
        return
    cc = {'A': [], 'B': []}
    f = 0
    e = 0
    for i in range(1, len(s) - 1):
        if s[i] == s[i - 1]:
            l = i - f
            if l % 2 == 0:
                cc[s[f]].append(l // 2)
            else:
                e += l // 2
            f = i
    l = len(s) - 1 - f
    if l % 2 == 0:
        cc[s[f]].append(l // 2)
    else:
        e += l // 2
    ca = cc['A']
    ca.sort(reverse=True)
    while ca and c > 0:
        w = min(ca[-1], c)
        ca[-1] -= w
        c -= w
        if ca[-1] == 0:
            ca.pop()
    cb = cc['B']
    cb.sort(reverse=True)
    while cb and d > 0:
        w = min(cb[-1], d)
        cb[-1] -= w
        d -= w
        if cb[-1] == 0:
            cb.pop()
    for i in ca:
        e += i - 1
    for i in cb:
        e += i - 1
    if c + d <= e:
        print('YES')
    else:
        print('NO')

def main():
    for i in range(int(sys.stdin.readline())):
        solve()
if __name__ == '__main__':
    main()

Solution (Python):
for _ in range(int(input())):
    (a, b, ab, ba) = map(int, input().split())
    s = input()
    if s.count('A') != a + ab + ba:
        print('NO')
        continue
    stack = [[1, s[0]]]
    for i in range(1, len(s)):
        if stack[-1][1] != s[i]:
            x = stack.pop()
            stack.append([x[0] + 1, s[i]])
        else:
            stack.append([1, s[i]])
    stack.sort()
    trash = 0
    for (val, ele) in stack:
        if not val % 2:
            if ele == 'A' and ba >= val // 2:
                ba -= val // 2
            elif ele == 'B' and ab >= val // 2:
                ab -= val // 2
            else:
                trash += val // 2 - 1
        else:
            trash += val // 2
    print('YES' if trash >= ab + ba else 'NO')

Solution (Python):
for _ in range(int(input())):
    (a, b, ab, ba) = map(int, input().split())
    s = input()
    if s.count('A') != a + ab + ba:
        print('NO')
        continue
    stack = [[1, s[0]]]
    for i in range(1, len(s)):
        if stack[-1][1] != s[i]:
            x = stack.pop()
            stack.append([x[0] + 1, s[i]])
        else:
            stack.append([1, s[i]])
    stack.sort()
    trash = 0
    for (val, ele) in stack:
        if not val % 2:
            if ele == 'A' and ba >= val // 2:
                ba -= val // 2
            elif ele == 'B' and ab >= val // 2:
                ab -= val // 2
            else:
                trash += val // 2 - 1
        else:
            trash += val // 2
    print('YES' if trash >= ab + ba else 'NO')