Class Solution

Python/longest-valid-parentheses.py:7–20

Space complexity: O(n)
'''
class Solution(object):
    def longestValidParentheses(self, s):
        ans=0
        stack=[-1]
        for i in range(len(s)):
            if(s[i]=='('):
                stack.append(i)
            else:
                stack.pop()
                if(len(stack)==0):
                    stack.append(i)
                else:
                    ans=max(ans,i-stack[-1])
        return ans