YetnotherrokenKeoard (Codeforces 1907B)
Tags: Implement, strings

Polycarp has a problem — his laptop keyboard is broken.Now, when he presses the 'b' key, it acts like an unusual backspace: it deletes the last (rightmost) lowercase letter in the typed string. If there are no lowercase letters in the typed string, then the press is completely ignored.Similarly, when he presses the 'B' key, it deletes the last (rightmost) uppercase letter in the typed string. If there are no uppercase letters in the typed string, then the press is completely ignored.In both cases, the letters 'b' and 'B' are not added to the typed string when these keys are pressed.Consider an example where the sequence of key presses was "ARaBbbitBaby". In this case, the typed string will change as follows: "" $$$\xrightarrow{\texttt{A}}$$$ "A" $$$\xrightarrow{\texttt{R}}$$$ "AR" $$$\xrightarrow{\texttt{a}}$$$ "ARa" $$$\xrightarrow{\texttt{B}}$$$ "Aa" $$$\xrightarrow{\texttt{b}}$$$ "A" $$$\xrightarrow{\texttt{b}}$$$ "A" $$$\xrightarrow{\texttt{i}}$$$ "Ai" $$$\xrightarrow{\texttt{t}}$$$ "Ait" $$$\xrightarrow{\texttt{B}}$$$ "it" $$$\xrightarrow{\texttt{a}}$$$ "ita" $$$\xrightarrow{\texttt{b}}$$$ "it" $$$\xrightarrow{\texttt{y}}$$$ "ity".Given a sequence of pressed keys, output the typed string after processing all key presses.

Input: The first line of the input data contains an integer $$$t$$$ ($$$1 \le t \le 1000$$$), the number of test cases in the test.The following contains $$$t$$$ non-empty lines, which consist of lowercase and uppercase letters of the Latin alphabet.It is guaranteed that each line contains at least one letter and the sum of the lengths of the lines does not exceed $$$10^6$$$.

Output: For each test case, output the result of processing the key presses on a separate line. If the typed string is empty, then output an empty line.


Sample Inputs:
12
ARaBbbitBaby
YetAnotherBrokenKeyboard
Bubble
Improbable
abbreviable
BbBB
BusyasaBeeinaBedofBloomingBlossoms
CoDEBARbIES
codeforces
bobebobbes
b
TheBBlackbboard

Sample Outputs:
ity
YetnotherrokenKeoard
le
Imprle
revile

usyasaeeinaedofloominglossoms
CDARIES
codeforces
es

helaoard

Solution (Python):
import sys
import sys

def out(v):
    sys.stdout.write(v)
import sys
import collections

def main():
    test = int(sys.stdin.readline().strip())
    for t in range(test):
        s = sys.stdin.readline().strip()
        temp = []
        il = 0
        ul = 0
        for i in s[::-1]:
            if i == 'B':
                ul += 1
            elif i == 'b':
                il += 1
            elif i.isupper():
                if ul > 0:
                    ul -= 1
                else:
                    temp.append(i)
            elif i.islower():
                if il > 0:
                    il -= 1
                else:
                    temp.append(i)
        print(''.join(temp[::-1]))
if __name__ == '__main__':
    main()

Solution (Python):
import math
import itertools

def check(myStr):
    stack = []
    open_list = ['(']
    close_list = [')']
    for i in myStr:
        if i in open_list:
            stack.append(i)
        elif i in close_list:
            pos = close_list.index(i)
            if len(stack) > 0 and open_list[pos] == stack[len(stack) - 1]:
                stack.pop()
            else:
                return False
    if len(stack) == 0:
        return True
    else:
        return False

def intlist():
    return [int(i) for i in input().split(' ')]

def stringlist():
    return input().split(' ')

def yess(t):
    if t:
        return 'YES'
    return 'NO'

def printjoin(l, str=False):
    if str:
        l = [str(i) for i in l]
    return ' '.join(l)

def power_of_two(n):
    b = bin(n)[2:]
    return int(b) == 10 ** (len(b) - 1)

def bit_count(n):
    return bin(n).count('1')

def gcd(x, y):
    while y:
        (x, y) = (y, x % y)
    return x

def is_prime(n):
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

def lcm(x, y):
    lcm = x * y // gcd(x, y)
    return lcm

def removebyindex(S, Index):
    S = S[:Index] + S[Index + 1:]
    return S

def isint(str):
    try:
        int(str)
        return True
    except ValueError:
        return False
yes = 'YES'
no = 'NO'

def solve():
    s = input()
    ans = ''
    s = s[::-1]
    low = 0
    cap = 0
    for i in s:
        if i == 'b':
            low += 1
        elif i == 'B':
            cap += 1
        elif i.islower():
            if low:
                low -= 1
            else:
                ans += i
        elif cap:
            cap -= 1
        else:
            ans += i
    return ans[::-1]
t = input()
for tt in range(int(t)):
    print(solve())

Solution (Python):
""""""
from collections import deque

def solve():
    for _ in range(ii()):
        s = list(input())
        n = len(s)
        uc_idx = deque()
        lc_idx = deque()
        for i in range(n):
            if s[i] == 'B':
                s[i] = ''
                if uc_idx:
                    s[uc_idx.pop()] = ''
            elif s[i] == 'b':
                s[i] = ''
                if lc_idx:
                    s[lc_idx.pop()] = ''
            elif 'a' <= s[i] <= 'z':
                lc_idx.append(i)
            else:
                uc_idx.append(i)
        print(''.join(s))
if __name__ == '__main__':
    ii = lambda : int(input())
    mi = lambda : map(int, input().split())
    li = lambda : list(mi())
    si = lambda : input()
    solve()