Linguistics
Contest: Codeforces Round 794 (Div. 1)
Difficulty rating: 2000
Tags: greedy, implementation, sortings, 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 format:
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 format:
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.

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

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}$$$.

Example input:
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

Example output:
NO
YES
YES
YES
YES
YES
NO
YES

Editorial:
For the answer to be $$$\texttt{YES}$$$ the frequency of the character $$$\texttt{A}$$$ in the $$$a+b+c+d$$$ words must coincide with its frequency in the sentence $$$s$$$, which is equivalent to the condition $$$a + c + d = \#\{i:\, s_i = \texttt{A}\}$$$. From now on we may assume that this is true.
Notice that the answer to the problem is $$$\texttt{YES}$$$ if and only if it is possible to tile the string $$$s$$$ with $$$c$$$ copies of $$$\texttt{AB}$$$ and $$$d$$$ copies of $$$\texttt{BA}$$$ so that all the $$$c+d$$$ substrings are disjoint. Indeed one can simply fill the remaining characters of $$$s$$$ with the $$$a$$$ copies of $$$\texttt{A}$$$ and the $$$b$$$ copies of $$$\texttt{B}$$$ (we are sure that the number of characters $$$\texttt{A}$$$ and $$$\texttt{B}$$$ is correct because of the initial check). Moreover, if $$$s_i = s_{i+1}$$$, then clearly any tiling with $$$\texttt{AB}$$$ and $$$\texttt{BA}$$$ of $$$s$$$ cannot cover with a single tile both $$$s_i$$$ and $$$s_{i+1}$$$; therefore we can split the string $$$s$$$ between $$$s_i$$$ and $$$s_{i+1}$$$ and try to tile the two resulting substrings. By repeating this argument we will end up with many alternating strings (a string $$$t$$$ is alternating if $$$t_{i} \not= t_{i+1}$$$ for all $$$1\le i < |t|$$$). So, we have reduced the problem to the following one:
Subproblem: You are given many alternating strings, can you find in these strings $$$c$$$ substrings equal to $$$\texttt{AB}$$$ and $$$d$$$ subtrings equal to $$$\texttt{BA}$$$ such that all the $$$c+d$$$ substrings are disjoint?
In order to solve the problem let us analyze what happens when only one alternating string is present. Given an alternating string $$$t$$$, we say that the pair $$$(x, y)$$$ is valid if we can find in $$$t$$$ $$$x$$$ substrings equal to $$$\texttt{AB}$$$ and $$$y$$$ substrings equal to $$$\texttt{BA}$$$ so that the $$$x+y$$$ substrings are disjoint. Let us consider various cases:
1. If $$$|t|=2k+1$$$, then $$$(x, y)$$$ is valid if and only if $$$x + y \le k$$$. Let $$$f(k):=\{(x, y):\, 0\le x,y\text{ and } x + y\le k\}$$$.
2. If $$$|t|=2k$$$ and $$$t_1 = \texttt{A}$$$, then $$$(x, y)$$$ is valid if and only if $$$x+y\le k-1$$$ or $$$(x, y) = (k, 0)$$$. Let $$$f_{AB}(k):= \{(k, 0)\}\cup f(k-1)$$$.
3. If $$$|t|=2k$$$ and $$$t_1 = \texttt{B}$$$, then $$$(x, y)$$$ is valid if and only if $$$x+y\le k-1$$$ or $$$(x, y) = (0, k)$$$. Let $$$f_{BA}(k):= \{(0, k)\}\cup f(k-1)$$$.
We will provide a proof for the correcteness of the following greedy algorithm.
Greedy algorithm: Sort the strings of type $$$2$$$ by length and fill them, starting from the shortest, only with $$$\texttt{AB}$$$ (i.e., find as many disjoint copies of $$$\texttt{AB}$$$ as possible) until you reach $$$c$$$ or you finish them (a string of length $$$2k$$$ is filled with $$$k$$$ $$$\texttt{AB}$$$). Do the same for the strings of type $$$3$$$ for the word $$$\texttt{BA}$$$. At this point there are no more bonuses to use and you can just fill the remaining strings with $$$\texttt{AB}$$$ and $$$\texttt{BA}$$$ in the only reasonable way. If in the end, if you have found $$$c$$$ strings $$$\texttt{AB}$$$ and $$$d$$$ strings $$$\texttt{BA}$$$ then the answer is $$$\texttt{YES}$$$, otherwise it is $$$\texttt{NO}$$$.
Let us provide a proof of the correctness of this algorithm. Let us remark that the proof of the correctness is in fact rather easy, but a bit cumbersome to write down. The strategy of the proof is to start from a solution and to show that the one constructed by the greedy algorithm is "better".
Proof of the correctness of the greedy algorithm: Let $$$U, V, W$$$ be the multisets of lengths of strings of the first, second and third type respectively (according to the case division above). Then the problem is equivalent to understanding if $$$$$$ (c, d) \in \sum_{u\in U} f(u) + \sum_{v\in V} f_{AB}(v) + \sum_{w\in W} f_{BA}(w). $$$$$$
Assume that the answer is $$$\texttt{YES}$$$ and consider a solution of the problem, i.e. a choice of a valid pair for each of the $$$|U|+|V|+|W|$$$ alternating strings. Let $$$V = V'\sqcup V' '$$$ where $$$V'$$$ corresponds to the lengths of the strings in $$$V$$$ where the valid pair of the solution is given by $$$(k, 0)$$$ ($$$k$$$ is the length of the string). Partition $$$W=W'\sqcup W' '$$$ analogously. Then we have $$$$$$ (c, d) \in \sum_{u\in U} f(u) + \sum_{v'\in V'} (v', 0) + \sum_{v' '\in V' '} f(v' ' - 1) + \sum_{w'\in W'} (0, w') + \sum_{w' '\in W' '} f(w' ' - 1) . $$$$$$
Let us make a couple of observations:
• For any $$$k_1, k_2$$$ it holds $$$f(k_1) + f(k_2) = f(k_1 + k_2)$$$.
• If $$$k_1\le k_2$$$, then $$$f(k_1) + (k_2, 0) \subseteq (k_1, 0) + f(k_2)$$$ and also $$$f(k_1) + (0, k_2) \subseteq (0, k_1) + f(k_2)$$$.