[note: my solution is NOT UNIQUE. If you’ve read the editorial, you’ll find my approach quite similar. But I’m still writing it because for some, the editorial might be slightly unclear. (At least for me!)]
Short description: The problem gives you a bracket sequence S and Q number of queries t_i. For each t_i, you have to check if it is possible to form a complete bracket sequence using all the characters S[t_i],S[t_i +1],… S[|S|] . Here |S| means length of S. If not possible, print -1. Else, find the minimum index j such that S[t_1],S[t_i +1]…S[j] is a complete bracket sequence.We can omit some closing parenthesis but not opening parenthesis.
HOW TO SOLVE: Indeed this is a good implementation of stack. You must be familiar with the technique of checking the validity of a bracket sequence using stack.
If not… https://www.geeksforgeeks.org/check-for-balanced-parentheses-in-an-expression/
Now here’s what er do… we take a stack st and an array prec. Initially all the value of prec will be -1.
Now we do the sequence checking technique. But with a slight twist!
We traverse the sequence. If we get an opening bracket, we push ITS INDEX to the stack. Else, if we get a closing bracket and the stack is empty, there’s nothing we can do. But if not,
say, the index of the opening parenthesis is cur and we surely know that the top of the stack has the index of the nearest opening parenthesis. Say top of the stack is top. What we do now is that, prec[cur]=cur+1, prec[top]=cur+1. This means that if we are at position cur or at top, the nearest position to get a complete bracket sequence is cur+1 since it is 1- based.
Our job is almost done. But problem also says that we can omit some closing parenthesis. so what about that? Simple. We traverse the array prec backwards. Let a variable be id=-1. If we get a opening parenthesis at index i, we set id=prec[i].
Else prec[i]=id. This is because if we start from a closing parenthesis, we need to go to the nearest opening parenthesis and the find our result. So after calculating the results, we forward the results of the opening brackets to its nearest previous opening bracket.
def solve(): s=input() stack= dp=[-1]*(len(s)) for cur in range(len(s)): if s[cur]=='(': stack.append(cur+1) else: if len(stack)==0: continue d=stack[-1]-1 dp[cur]=cur+1 dp[d]=cur+1 stack.pop() ln=len(s) cur=-1 for n in range(ln-1,-1,-1): if s[n]==')':dp[n]=cur else:cur=dp[n] (input()) s=list(map(int,input().split())) for n in s: print(dp[n-1]) for n in range(int(input())):solve()