Use a stack for the sequence. If it is a “(“ push its index in. If it is a “)”, check if the top element is a “(“. If so pop it. Otherwise, push the “)” index in. After we walked through the whole sequence. The stack is a list of the indices of the illegal characters. We just go through it to find the longest gap between two neighbours.
class Solution(object): def longestValidParentheses(self, s): """ :type s: str :rtype: int """ stk =  for i, ch in enumerate(s): if ch == '(': stk.append(i) elif stk and s[stk[-1]] == '(': stk.pop() else: stk.append(i) stk.append(len(s)) stk = [-1] + stk ret = 0 for i in range(len(stk) - 1): ret = max(ret, stk[i + 1] - stk[i] - 1) return ret