Linguistics (Codeforces 1686D)
Tags: Greedy, two pointers

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
input = sys.stdin.readline

def solve():
    (a, b, c, d) = map(int, input().split())
    s = input().strip()
    n = len(s)
    cnt = 0
    for i in range(n):
        if s[i] == 'A':
            cnt += 1
    if cnt != a + c + d:
        return 'NO'
    prev = -1
    cnt = 0
    r = []
    for i in range(n):
        if prev == s[i]:
            r.append((cnt, prev))
            cnt = 1
        else:
            cnt += 1
            prev = s[i]
    r.append((cnt, prev))
    r.sort()
    e = 0
    for (length, lc) in r:
        if length % 2 == 0:
            if lc == 'B' and length // 2 <= c:
                c -= length // 2
            elif lc == 'A' and length // 2 <= d:
                d -= length // 2
            else:
                e += length // 2 - 1
        else:
            e += length // 2
    return 'YES' if e >= c + d else 'NO'
for _ in range(int(input())):
    print(solve())

Solution (Python):
import sys

def rall():
    return sys.stdin.readlines()

def rl():
    return sys.stdin.readline().strip()

def rl_types(types):
    str_list = [x for x in sys.stdin.readline().strip().split(' ')]
    return [types[i](str_list[i]) for i in range(len(str_list))]

def pr(something=''):
    sys.stdout.write(str(something) + '\n')

def pra(array):
    sys.stdout.write(' '.join([str(x) for x in array]) + '\n')

def solve(array):
    return array
if __name__ == '__main__':
    NT = int(rl())
    for ti in range(NT):
        raw = list(map(int, rl().split(' ')))
        (nA, nB, nAB, nBA) = raw
        st = rl()
        array = [0 if c == 'A' else 1 for c in st]
        (numBs, numAs) = (sum(array), len(array) - sum(array))
        alt_groups = []
        last = -1
        alt_len = 0
        for (i, v) in enumerate(array):
            if last < 0:
                last = v
                alt_len = 1
            elif last == v:
                last = v
                if alt_len > 1:
                    alt_groups.append((array[i - alt_len], alt_len))
                alt_len = 1
            else:
                last = v
                alt_len += 1
        if alt_len > 1:
            alt_groups.append((array[len(array) - alt_len], alt_len))
        either = 0
        optA = []
        optB = []
        for (s, l) in alt_groups:
            if l % 2 == 1:
                either += l // 2
            elif s == 0:
                optA.append(l // 2)
            else:
                optB.append(l // 2)
        optA.sort()
        optB.sort()
        for oa in optA:
            if nAB >= oa:
                nAB -= oa
            else:
                either += oa - 1
        for ob in optB:
            if nBA >= ob:
                nBA -= ob
            else:
                either += ob - 1
        possible = nAB + nBA <= either
        if possible:
            (nA, nB, nAB, nBA) = raw
            pairs = nAB + nBA
            if not (numAs == nA + pairs and numBs == nB + pairs):
                possible = False
        print('YES' if possible else 'NO')

Solution (Python):
import decimal
import gc
import heapq
import math
import os
import random
import sys
from collections import Counter, deque, defaultdict
from io import BytesIO, IOBase
import bisect
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def isPrime(n):
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i = i + 6
    return True

def lcm(a, b):
    return a * b // math.gcd(a, b)

def ciel(a, b):
    x = a // b
    if a % b == 0:
        return x
    return x + 1

def ints_get():
    return map(int, input().strip().split())

def list_get():
    return list(map(int, sys.stdin.readline().strip().split()))

def chars_get():
    return list(map(str, sys.stdin.readline().strip().split()))

def ipn():
    return int(input())

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc

def main():
    for _ in range(ipn()):
        (a, b, c, d) = ints_get()
        v = [x for x in input()]
        (x, y, z) = (0, [], [])
        s = ''
        for i in range(len(v)):
            if len(s) == 0:
                s += v[i]
            elif s[-1] == v[i]:
                if len(s) < 2:
                    pass
                elif len(s) % 2 != 0:
                    x += len(s) // 2
                elif s[0] == 'A':
                    y.append(len(s))
                else:
                    z.append(len(s))
                s = v[i]
            else:
                s += v[i]
        if len(s) % 2 != 0:
            x += len(s) // 2
        elif s[0] == 'A':
            y.append(len(s))
        else:
            z.append(len(s))
        y.sort()
        z.sort()
        (e, f) = (c, d)
        for i in range(len(y)):
            if c > 0:
                w = min(c, y[i] // 2)
                c -= w
                y[i] -= 2 * w
            if c == 0 and d > 0:
                w = min(d, y[i] // 2 - 1)
                w = max(w, 0)
                d -= w
        for i in range(len(z)):
            if d > 0:
                w = min(d, z[i] // 2)
                d -= w
                z[i] -= 2 * w
            if d == 0 and c > 0:
                w = min(c, z[i] // 2 - 1)
                w = max(w, 0)
                c -= w
        if c + d <= x and v.count('A') == a + e + f and (v.count('B') == b + e + f):
            print('YES')
        else:
            print('NO')
    return
if __name__ == '__main__':
    main()