**PROBLEM LINK**

**Author:** Aman Kumar Singh

**Tester:** Sarthak Manna, Smit Mandavia, Avijit Agarwal

**Editorialist:** Avijit Agarwal

**DIFFICULTY**

Easy

**PREREQUISITES**

Stacks

**PROBLEM**

You are given a string S of length N consisting only of opening brackets ( and closing brackets ). Consider Q cases. In the i^{\text{th}} case, Chef appears at time t_i and faces all characters from index t_i to N. Find the minimum index x (ti≤x≤N) such that the substring S_{t_i..x} contains a valid non-empty bracket subsequence. However, the valid subsequence must contain the same number of opening brackets as the substring S_{t_i ... x}, ie, you cannot remove any opening bracket from the substring. If such an x does not exist, print -1.

**EXPLANATION**

The time t_i is completely analogous to the position t_i in the string S. The first thing to observe is that the valid non-empty bracket subsequence must be a substring as it needs to have all the opening brackets in S_{t_i ... x} and thus leaving out a closing bracket would not minimize x. A valid bracket substring must start with an opening bracket. So we need to find the first opening bracket which appears on or after the position t_i in the string S. We can do it easily by iterating from N to 1 and assign the last occurence of an opening bracket to the current position. Let us call the position of this first opening bracket on or after the position t_i as z.

So now the job is reduced to finding a valid non empty bracket substring S_{z..x} where x should be minimal. This can be done easily using a simple stack operation. We maintain a stack which contains only the positions of opening bracket from the first position of an array. If we encounter an closing bracket at a position x, we pop the top of the stack containing the position z and assign x as the minimal position such that S_{z..x} is a valid non empty bracket substring.

The time complexity required is \mathcal{O}(N+Q)

### SOLUTIONS

C++ solution can be found here.

Java solution can be found here.

Python solution can be found here.