Longest Valid Parentheses
1. Review


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.
There is no need for the special case:

if len(s) &lt;= 1: return 0


since these cases are handled correctly by the rest of the code.
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.
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.

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

The test i-longest[i-1]-2 &gt;= 0 becomes j-1 &gt;= 0 and this can be simplified to j &gt; 0 to avoid the subtraction, and then just to j since you have already tested j &gt;= 0.
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.
The line:

if longest[i] &gt; max_len: max_len = longest[i]


can be simplified using the built-in max:

max_len = max(max_len, longest[i])

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 &gt;= 0 and s[j] == '(':
            longest[i] = 1 + i - j + longest[j-1]
return max(longest, default=0)