[LeetCode] 32. Longest Valid Parentheses

Problem : https://leetcode.com/problems/longest-valid-parentheses/

Consider DP[i] = the longest valid parentheses ends with s[i].

To make a valid parentheses pair, s[i] must be ')'.

When S[i-1] = '(':      # ****()

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

When S[i-1] = ')'  And S[i - DP[i-1] - 1] == '(':    # ***((***))

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

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

A Top-Down approach:

class Solution:
    def longestValidParentheses(self, s: str) -> int:

        @lru_cache(maxsize = None)
        def helper(i):
            if i <= 0 or s[i] == '(': return 0
            
            # s[i] == ')'            
            if i - 1 >= 0:
                if s[i-1] == '(':
                    return helper(i-2) + 2
                else:
                    # s[i-1] == ')'
                    n = helper(i-1)
                    
                    if n > 0:
                        left = i - n - 1
                        if left >= 0 and s[left] == '(':
                            return helper(left-1) + 2 + helper(i-1)
            
            return 0
        
        N = len(s)
        return max(map(helper, range(N))) if N > 0 else 0

Edit on 04/03/2021. Add the Top-Down approach.