Longest Valid Parentheses



@alexh95
It is correct. Output of ")(" is 0. The condition if(right>left) right=left=0 will handle this example.

@MitchellHe
Consider the input "(()" , left to right scan will output 0, but the answer is 2.

The dp approach maybe can simplify the IF condition of s[i1] == '(' or ')'
just consider the s[i1] == '(' is a kind of situation that dp[idp[i1]2] + dp[i1] + 2
means that there is no Parenthese between '('(s[idp[i1]1]) and ')'(s[i])
Python Solutionclass Solution(object): def longestValidParentheses(self, s): """ :type s: str :rtype: int """ n = len(s) dp = [0]*n ret = 0 for i in range(n): if s[i] == ')': if i  dp[i1] > 0 and s[idp[i1]1] == '(': dp[i] = (dp[idp[i1]2] if i  dp[i1] > 1 else 0) + dp[i1]+2 ret = max(ret, dp[i]) return ret




So I had hard time understanding "stack" approach. Thank you for sharing.
For others who're also struggling to understand stack approach. Stack at any given point contains an index "after which valid substring could potentially start".
So begins with 1 (optimistically valid substring could start with 0 index)
Whenever "(" is encountered, assuming valid substring will begin after "(" (but excluding current "("'s position).
Whenever ")" is encountered, top of stack is pooped  this takes care of immediately previous "(" but optimistic assumption of immediately previous's previous "("'s index came true. So length is current index  top of stock. "(" always assume that valid string will be "after" "(", ")" pop top of stack (if not empty) and find length of valid string found. If ")" is encountered with empty stack. Assume valid string will begin after ")".Cumulative pushing "(" (or ")" if stack is empty) takes care of extending substring with balanced parentheses.