### Problem Link

### Tutorial

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.

### Solution

```
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
```