Longest Valid Parenthesis

'''
Solution (Simulating with stack) :

We can use a stack to find the longest valid parentheses.

We will start by pushing -1 into the stack at first. This will denote index preceding to potential start of valid parentheses. It will be more clear later. Now will start iterating over s and we will have two cases -

s[i] == '(' - In this case, we will push the index into the stack (just as we do in valid parentheses check).
s[i] == ')' - In this case, we will pop the index from the stack (again just as in parentheses check). Now, after popping, we need to do some simple checks which are main steps of this problem. Again, there will be following scenarios that may occur -
1)stack is not empty - If stack is not empty, then this may be our longest valid parentheses. We update the MAX_len as max(MAX_len, current index - stack.top()). Do notice, that our bottom of stack will always hold index preceding to a potential valid parentheses.
2)stack becomes empty - This will only happen when we have an extra ')' bracket. There may have been valid parentheses previously which have been updated and stored in MAX_len. But, since we now have an extra closing bracket any further extensions of previous valid parentheses is not possible. So, push the current index into stack, again which will denote that bottom of stack will hold the index preceding to a potential valid parentheses.
'''
# User function Template for Python3

class Solution:
    def maxLength(self, s):
        ans=0
        st=[-1]
        n=len(s)
        for i in range(n):
            if s[i]=='(':
                st.append(i)
            else:
                st.pop()
                if not st:
                    st.append(i)
                ans=max(ans,i-st[-1])
        return ans