Longest Valid Parentheses

Question

This is the "Longest Valid Parentheses" problem from leetcode.com:

Given a string containing just the characters "(" and ")", find the length of the longest valid (well-formed) parentheses substring. For "(()", the longest valid parentheses substring is "()", which has length 2. Another example is ")()())", where the longest valid parentheses substring is "()()", which has length 4.

I was studied this interview question during mock-interview. And I was able to test it against the test cases.

Start from the longest length, and use a stack to identify if it is valid. If not, length - 1.

Put the elements index in the string into a stack, if "(" then add to the stack. If ")" if stack not empty, if s[stack.top()] == "(", stack.pop(), else stack.push(i). If stack is empty, stack.push(i).

The most important idea is that the substring between the adjacent indices in stack is valid.The most important aspect with dynamic programming is what the subscript j represent. Let longest be the array for dp. longest[i] is the longest substring end with i.

def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: 
        """
        if len(s) <= 1: return 0
        longest = [0] * len(s)
        max_len = 0
        for i in range(1, len(s)):
            if s[i] == ")":
                if s[i-1] == "(":
                    longest[i] = 2 + (longest[i-2] if i - 2>= 0 else 0)
                    print "hrere"
                    print longest[i]
                    if longest[i] > max_len: max_len = longest[i]
                else:
                    if i - longest[i-1] - 1 >= 0 and s[i-longest[i-1]-1] == "(":
                        longest[i] = 2 + longest[i-1] + (longest[i-longest[i-1]-2] if i-longest[i-1]-2 >= 0 else 0)
                        if longest[i] > max_len: max_len = longest[i]
        return max_len

Answer 1

1. Review

1. There are a couple of print statements that seem to be left over from a debugging session. If you want to trace the execution of a Python program, you can do so without editing the code, by using the Python debugger. This would avoid the risk of forgetting to remove your debugging code.

2. There is no need for the special case:

   if len(s) <= 1: return 0
   

   since these cases are handled correctly by the rest of the code.

3. There is also no need for the special case:

   if s[i-1] == "(":
   

   since if you look at the two branches you'll see that they do the same thing.

4. The algorithm is slightly tricky so I would like to have a comment explaining the values that we are going to put in the array longest:

   # longest[i] will be length of longest valid substring ending at i.
   

5. The expression i - longest[i-1] - 1 appears in several places so would benefit from being stored in a variable:

   # Index where matching ( would have to be, if it exists.
   j = i - longest[i-1] - 1
   

6. The test i-longest[i-1]-2 >= 0 becomes j-1 >= 0 and this can be simplified to j > 0 to avoid the subtraction, and then just to j since you have already tested j >= 0.

7. We can avoid testing j at all by noting that if it is 0 then j-1 is -1 and longest[-1] is still a valid lookup, getting the last entry of the array longest, which is 0 as required.

8. The line:

   if longest[i] > max_len: max_len = longest[i]
   

   can be simplified using the built-in max:

   max_len = max(max_len, longest[i])
   

9. Instead of maintaining a running maximum, just run max once at the end:

   return max(longest, default=0)
   

   This requires Python 3.4 or later, for the default argument. On earlier versions of Python you'd have to write something like:

   return max(longest) if longest else 0
   

2. Revised code

# longest[i] will be length of longest valid substring ending at i.
longest = [0] * len(s)
for i in range(1, len(s)):
    if s[i] == ')':
        # Index where matching ( would have to be, if it exists.
        j = i - longest[i-1] - 1
        if j >= 0 and s[j] == '(':
            longest[i] = 1 + i - j + longest[j-1]
return max(longest, default=0)