1 class Solution:
 2     # @param s, a string
 3     # @return an integer
 4     def longestValidParentheses(self, s):
 5         if s == ‘‘ or s == ‘(‘ or s == ‘)‘:
 6             return 0
 7         stack = [(-1, ‘)‘)]
 8         maxLen = 0
 9         for i in xrange(len(s)):
10             if s[i] == ‘)‘ and stack[-1][1] == ‘(‘:
11                 stack.pop()
12                 maxLen = max(maxLen, i - stack[-1][0])
13             else:
14                 stack.append((i, s[i]))
15         return maxLen
16 # test
17 s = Solution()
18 print s.longestValidParentheses("()(()")
19 print s.longestValidParentheses(‘(()()‘)
20 print s.longestValidParentheses(‘)()())‘)