This is the "Longest Valid Parentheses" problem from leetcode.com:
Given a string containing just the characters
")", 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.push(i). If stack is empty,
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 =  * 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