Longest Valid Parentheses

Description

Given a string containing just the characters ‘(’ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.

Example 1:

1
2
3


Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"

Example 2:

1
2
3


Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"

Dynamic Programming Solution

Let $dp[i]$ to be the length of the longest valid parentheses which ends at $i$‘th position.

$s[i]$ must be ) to have a valid parentheses, else $dp[i] = 0$

Depends on s[i-1], we have 2 situations:

$s[i-1] = ($

…	i-2	i-1	i
…	.	(	)
	dp[i-2]	0	dp[i]

1

dp[i] = dp[i-2] + 2

$s[i-1] = )$ we have 2 situations, only needs to consider $s[i-dp[i-1]-1] = ($

i-dp[i-1]-2	i-dp[i-1]-1	i-dp[i-1]	…	i-1	i
?	(	(	…	)	)
dp[i-dp[i-1]-2]	0	0	…	dp[i-1]	dp[i]

1

dp[i] = dp[i-dp[i-1]-2] + dp[i-1] + 2

Combining all the situations above, we have:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution:
    def longestValidParentheses(self, s: str) -> int:
        n = len(s)
        dp = [0]*n
        _max = 0
        for i in range(n):
            if s[i] == ')' and (i-1>=0):
                if s[i-1] == '(':
                    dp[i] = (dp[i-2] if (i-2>=0) else 0) + 2
                    _max = max(_max, dp[i])
                else:
                    if (i-dp[i-1]-1>=0) and s[i-dp[i-1]-1] == '(':
                        dp[i] = dp[i-1] + 2 + (dp[i-dp[i-1]-2] if (i-dp[i-1]-2>=0) else 0)
                        _max = max(_max, dp[i])

        return _max

Though the DP solution is not quite intuitive for me.

Stack Solution

Maintain a stack, which borrows the idea from Valid Parentheses

When a ( arrives, push it into the stack
When a ) arrives, compare it with the top of stack, if it forms a pair, pop it, else push it.
After the whole process, the items left in the stack are those not having valid pairs. On the other side, other elements are valid pairs. We just need to find longest space between those elements in the stack. So we push index of the elements, instead of the element itself.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution:
    def longestValidParentheses(self, s: str) -> int:
        stack: List[int] = []
        max_len: int = 0
        for i in range(len(s)):
            if s[i] == '(':
                stack.append(i)
            elif s[i] == ')':
                if stack and s[stack[-1]] == '(':
                    stack.pop()
                    last_not_paired = stack[-1] if stack else -1
                    max_len = max(max_len, i-last_not_paired)
                else:
                    stack.append(i)
        return max_len

Notes

We generate the max length on the fly. Each time a pair generated, we calculate space between current element and last element remains in the stack, which is the last index that has not been paired yet, which is the current length of the generated valid substring.
Watch out for corner case: if the stack is empty, we cannot find last element that has not been pairs, just put -1 to it shoud be fine.