# Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
#
# For "(()", the longest valid parentheses substring is "()", which has length = 2.
#
# Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.
class Solution(object):
def longestValidParentheses(self, s):
"""
:type s: str
:rtype: int
"""
stack = []
maxlen = 0
start = -1
for i, c in enumerate(s):
if c=='(':
if start>=0:
stack.append((c, start))
start = -1
else:
stack.append((c, i))
else:
if stack and stack[-1][0]=="(":
length = i-stack[-1][1]+1
if length>maxlen:
maxlen = length
start = stack[-1][1]
stack.pop()
else:
start = -1
stack.append((c, i))
return maxlen
if __name__ == "__main__":
assert Solution().longestValidParentheses("()") == 2
assert Solution().longestValidParentheses(")()())") == 4