32. Longest Valid Parentheses

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

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.

  1. () 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.
  2. …))

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

Using Stack

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax