[Leetcode] Longest Valid Parentheses

I really enjoyed solving this problem. The debugging process let me see the fallacies my thought has been. 

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.

---

We are not unfamiliar with this kind of problems: "longest increasing subsequence", "longest palindrome substring", "max money we can rob". All these questions fall to dynamic programming category. Easy or common dynamic programming isn't hard to understand or even to conceive one compared to greedy problems, IMAO, but it takes practice.

The key to dynamic programming is to have a recurrence formula. When designing it, think about what kind of variables or current we need to know to get the next state. Of course, this variable has to help you get the final answer.

In this problem, a first thought would be devise a DP array that stores the length of longest valid parentheses (LVP).  However, if we know the s[i]'s LVP, it seems not helping me to know s[i+1]'s LVP, because the matching pair would be far back. But we are asking substring, meaning that if s[i] is in a solution, then s[i+1] might be in the solution, and the s[i+1]'s matching pair should be the one back s[i]'s matching pair. Therefore, if we record the s[i] matching pair's position, we would be able to know s[i+1]'s matching pair. If it doesn't match anything, then we just make the index its value.

Okay, now we have an array dp, which stores the index of the matching pair. So far so good. But it can't handle "()()" situation. Yes, I realize it from testing...

So the next step is to integrate the dp array. Here is the code:

class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        if len(s) == 1: return 0
        # first round to get the position of the matching pair
        dp = [i for i in range(len(s))]
        for i in range(1, len(s)):
            if s[i] == '(':
                continue
            k = i - 1
            while dp[k] != k and k > 0:
                k = dp[k] - 1
            if s[k] == '(' and k >= 0:
                dp[i] = k
            else:
                dp[i] = i
        # second round to get the final answer, basically
        # to connect case like this: "()()"
        i = len(s) - 1
        res = 0
        while i > 0:
            if dp[i] != i:
                tmp_res, k = 0, i
                while dp[k] != k and k > 0:
                    tmp_res += (k - dp[k] + 1)
                    k = dp[k] - 1
                res = max(res, tmp_res)
                i = k
            else:
                i -= 1
        return res