Problem 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: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".

Example 2:

1
2
3
Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".

Example 3:

1
2
Input: s = ""
Output: 0

Constraints:

  • 0 <= s.length <= 3 * 104
  • s[i] is '(', or ')'.

Solution:

  1. Only need length of valid, so dp might be better
  2. Calculate length when find a ) at s[i], and there’re two subcases
    1. s[i-1] = (, it could form a valid with s[i]
    2. s[i-1] = ), we need to find previous not used (. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        # dp array to keep the longest valid at s[i]
        # if s[i] == ')' and s[i-1] == '(', then dp[i] = dp[i-2]+2
        
        
        dp = [0]* len(s)
        res = 0
        
        for i in range(1, len(s)):
            if s[i] == ')':
                if s[i-1] == '(': 
                    # case 1: ()()
                    dp[i] = dp[i-2] + 2
                elif i-dp[i-1]-1 >= 0 and s[i-dp[i-1]-1] == '(': 
                    # case 2: (()) 
                    # i-dp[i-1]-1 is the index of last "(" not paired until this ")"
                    # s[i-1] = ')', means it might have valid parenthese before it
                    dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2
                res = max(res, dp[i])
        return res

time complexity: $O(n)$
space complexity: $O(n)$
reference:
https://leetcode.com/problems/longest-valid-parentheses/discuss/14141/Pure-1D-DP-without-using-stack-(python)-with-detailed-explanation/14533
https://leetcode.com/problems/longest-valid-parentheses/discuss/14284/8-line-Python-solution-stack-80ms
https://leetcode-cn.com/problems/longest-valid-parentheses/solution/zui-chang-you-xiao-gua-hao-by-leetcode-solution/
related problem: