[Leetcode] Longest Valid Parentheses

Problem 

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.

Algorithm

1. DP

Claim 1: A valid parentheses must have the following form:

" ("   a shorter valid parathese   ")".

Claim 2: Two connected valid parentheses can be combined to a larger valid parentheses. 

Since this problem has a sub-optimal structure, we can solve it using DP. 

Let dp[i] be the length of the longest valid parentheses starting with s[i], end with s[i + dp[i] -1]. If dp[i] = 0, the valid parentheses start at i is empty. 

• Clearly, dp[n-1] = 0. 
• If s[i] = ")", dp[i] = 0;
• Else, let j = i+1+dp[i+1], if j >= n or s[j] != ")" , dp[i] = 0, since the "(" at i cannot find a match. If j+1 < n, we may connect the valid parentheses s[i ... j] and s[j ... dp[j]-1]. 

2. Stack

Maintain a stack to store the indices of unmatched brackets. Iterate the string, for each character

• If stack is empty, push its index 
• If it is "(", push its index
• If it is ")", and stack.peek() corresponds to a ")", push its index
• Otherwise, current character is a ")", and it matches with the top element of the stack. Therefore, we can pop the stack. The string start from stack.peek() +1 to current index is a valid parentheses, and we can update the maxLength so far. 

Code