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

Table of Contents

Use 1-D dynamic programming

We use 1D dynamic programming table to record the longest valid parenthesis ends at i. We observe that for a string of parenthesis to be valid, the string must ends on ‘)’. So we will only update the DP table if we see a ‘)’. There are two situations when we see a ) and it forms a valid parenthesis.

() if S[i – 1] == ‘(‘ and S[i] == ‘)’, then they form a valid parenthesis. We will then check DP[i – 2] to see if we can concatenate previous valid parenthesis in front of it.
…))

If S[i – 1] is ‘)’ then that means the valid parenthesis will be in the form of …)). So we first check if S[i – 1] is matched with another ‘(‘. We know the matched ‘(‘ will be at S[i – DP[i – 1]].

We then need to check does S[i – DP[i – 1] – 1] match with S[i]. If matched. Then the valid parenthesis that ends on i will be DP[i – 1] + 2 + DP[i – 2 – DP[i – 1]. The last section is to see if we can append any previous valid parenthesis to our current valid parenthesis. The previous valid parenthesis will end at i – 2 – DP[i – 1].

Code

    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        DP = [0 for _ in range(len(s) + 1)]

        for i in range(len(s)):
            #DP[i + 1] stores the longest valid paren ends at s[i]
            if s[i] == ')':
                if i > 0 and s[i - 1] == '(':
                    DP[i + 1] = DP[i - 1] + 2

                elif i > 0 and s[i - 1] == ')':
                    potential_matched_loc = i - DP[i + 1 - 1] - 1
                    #print('potential match at', i, potential_matched_loc)
                    if potential_matched_loc >= 0 and s[potential_matched_loc] == '(':
                        DP[i + 1] = DP[i] + 2 + DP[i + 1 - DP[i] - 2]

        #print(DP)
        return max(DP)

Implementation details

Use DP table of size len(s) + 1

The DP table is 1 larger than len(s) and DP[i + 1] will store the longest valid parenthesis ends at i. The extra slot at the beginning will be the base case so ()…. and ((…))… won’t need special treatment. Without the extra slot at the beginning, our code will try to access DP[-1]…

Bugs

Negative index!

Beware of it in python since python doesn’t throw warnings at that. at

if potential_matched_loc >= 0 and s[potential_matched_loc] == '(':

I first didn’t have potential_matched_loc >= 0 and when it takes input “(()))())(“, the code runs till index 4 and tries to find its match at position -1. It wrapped around and found the match at the end. ITS WRONG.

How do we know 2-d DP wouldn’t work

32. Longest Valid Parentheses