Recover an RBS (Codeforces 1709C)
Tags: Greedy, strings

A bracket sequence is a string containing only characters "(" and ")". A regular bracket sequence (or, shortly, an RBS) is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters "1" and "+" between the original characters of the sequence. For example:  bracket sequences "()()" and "(())" are regular (the resulting expressions are: "(1)+(1)" and "((1+1)+1)");  bracket sequences ")(", "(" and ")" are not. There was an RBS. Some brackets have been replaced with question marks. Is it true that there is a unique way to replace question marks with brackets, so that the resulting sequence is an RBS?

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 5 \cdot 10^4$$$) — the number of testcases.The only line of each testcase contains an RBS with some brackets replaced with question marks. Each character is either '(', ')' or '?'. At least one RBS can be recovered from the given sequence.The total length of the sequences over all testcases doesn't exceed $$$2 \cdot 10^5$$$.

Output: For each testcase, print "YES" if the way to replace question marks with brackets, so that the resulting sequence is an RBS, is unique. If there is more than one way, then print "NO".

Note: In the first testcase, the only possible original RBS is "(())".In the second testcase, there are multiple ways to recover an RBS.In the third and the fourth testcases, the only possible original RBS is "()".In the fifth testcase, the original RBS can be either "((()()))" or "(())()()".

Sample Inputs:
5
(?))
??????
()
??
?(?)()?)

Sample Outputs:
YES
NO
YES
YES
NO

Solution (Python):
from collections import Counter
from functools import lru_cache
import bisect
import math
import sys
result = []
input = sys.stdin.readline
LOG = 18
array = [1, 2, 3, 4, 5, 6, 7, 8]

def genSparseTable(array):
    sparseTable = [[float('inf') for i in range(LOG)] for x in range(len(array))]
    for i in range(len(array)):
        sparseTable[i][0] = array[i]
    for i in range(1, LOG):
        j = 0
        while j + (1 << i) - 1 < len(array):
            sparseTable[j][i] = max(sparseTable[j][i - 1], sparseTable[j + (1 << i - 1)][i - 1])
            j += 1
    return sparseTable

def query(l, r, sparseTable):
    length = r - l + 1
    idx = int(math.log(length, 2))
    return max(sparseTable[l][idx], sparseTable[r - (1 << idx) + 1][idx])
t = int(input())
for _ in range(t):
    string = input().rstrip()

    def solve():
        stack = []
        for (i, char) in enumerate(string):
            if char != ')':
                stack.append(i)
            else:
                if not stack:
                    return 'NO'
                stack.pop()
        if not stack:
            return 'YES'
        if len(stack) % 2 != 0:
            return 'NO'
        lastPos = len(stack) - 1
        ans = 'YES'
        state = False
        for i in reversed(range(len(string))):
            char = string[i]
            if char == '?':
                if stack[lastPos] <= i:
                    lastPos -= 2
                    if lastPos == -1:
                        if state:
                            return 'NO'
                        state = True
                        lastPos += 2
        return 'YES'
    ans = solve()
    print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
for t in range(int(input())):
    s = input().strip()
    n = len(s)
    open_brak = closed_brak = n >> 1
    for c in s:
        if c == '(':
            open_brak -= 1
        elif c == ')':
            closed_brak -= 1
    if not open_brak or not closed_brak:
        print('Yes')
        continue
    count = 0
    count_arr = [0] * n
    ans = 'Yes'
    question_mark = [None, None]
    for (idx, c) in enumerate(s):
        if c == '(':
            count += 1
        elif c == ')':
            count -= 1
        elif open_brak:
            open_brak -= 1
            count += 1
            if open_brak == 0:
                question_mark[0] = idx
        else:
            question_mark[1] = idx
            break
        count_arr[idx] = count
    ans = 'No'
    for i in range(*question_mark):
        if count_arr[i] < 2:
            ans = 'Yes'
            break
    print(ans)

Solution (Python):
import sys, math
input = sys.stdin.readline
INF = int(1000000000.0) + 7

def solve():
    s = input().rstrip()
    n = len(s)
    if n % 2 == 1:
        print('NO')
        return
    c = 0
    d = 0
    idx = -1
    for i in range(n):
        if s[i] == '?':
            d += 1
        elif s[i] == '(':
            c += 1
        else:
            c -= 1
    if d % 2 != c % 2 or abs(c) > d:
        print('NO')
        return
    if d == 0:
        print('YES')
        return
    if c >= 0:
        d = (d - c) // 2
    else:
        d = (d + c) // 2 - c
    a = [0] * n
    cur = 0
    for i in range(n):
        if s[i] == '(':
            cur += 1
        elif s[i] == ')':
            cur -= 1
        elif d:
            idx = i
            cur += 1
            d -= 1
        else:
            cur -= 1
        a[i] = cur
    ok = True
    if a[idx] < 2:
        ok = False
    for i in range(idx + 1, n):
        if s[i] == '?':
            if ok:
                print('NO')
                return
            else:
                break
        elif a[i] < 2:
            ok = False
    if n % 2 == 0 and a[n - 1] >= 0:
        print('YES')
        return
    print('NO')
t = 1
t = int(input())
for i in range(1, t + 1):
    solve()