Longest Valid Parentheses

Problem Id: 32 Difficulty: Hard Tag: String Tag: Dynamic Programming


Intuition

This problem is one of the hardest dynamic programming problems.

Let's define a dp array first. dp[i] indicates the longest valid parentheses that ends at i. Now let's discuss how to get dp[i], if dp[k] for any k that k < i has been calculated.

  1. The simplest case is that s[i] == '('. In this case, dp[i] = 0.
  2. If s[i] == ')', let's discuss 2 differnet cases.
    • If s[i - 1] == '(', like ....)(). Then dp[i] = dp[i - 2] + 2.
    • If s[i - 1] == ')', list ....(()) then we need to come to the previous character of the longest valid substring end with i - 1, and see if it is a (. If so, then dp[i] = dp[i - 1] + 2 + dp[prev - 1].

Solution


class Solution:
    def longestValidParentheses(self, s: str) -> int:
        dp = [0] * (len(s) + 1)
        for i, c in enumerate(s):
            if c == '(' or i == 0:
                continue
            if s[i - 1] == '(':
                dp[i] = 2 if i <= 2 else dp[i - 2] + 2
            else:
                prev = i - 1 - dp[i - 1]
                if prev >= 0 and s[prev] == '(':
                    dp[i] = dp[i - 1] + 2
                    if prev - 1 > 0 and s[prev - 1] == ')':
                        dp[i] += dp[prev - 1]
        return max(dp)