Leetcode: Longest Valid Parentheses

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.

Understand the problem:
The problem asks for finding the length of the longest valid parentheses substring. Note that it is substring not subsequence. 

Solution 1: Using DP
For those kinds of "longest substring" problems, it is usually to use DP solution. This problem is kind of special using the DP solution. 
1. Define dp[n], whereas dp[i] means the length of the longest valid parentheses substrings STARTING FROM i to str.length() - 1. 
2. Transit function. 
  -- If the str[i] = ')', dp[i] = 0, because there will no well-formed parentheses starting from ')'. 
  -- If the str[i] = '(', we check dp[i + 1], the longest valid parentheses starting from i + 1, and jump to the index j = i + dp[i + 1] + 1. e.g.
( ( ) ( ) )
i          j
So if j is within the length of the string and str[j] == ')', dp[i] = dp[i + 1] + 2. In addition, dp[i] += dp[j + 1], because what if after j the parentheses are still valid. 

3. Initial state: dp[n - 1] = 0
4. Final state: It is quite special here. We cannot check dp[0] because dp[i] stands for the length of longest valid parentheses starting from i. So the longest substring may not starts from str[0]. As a result, we must check if dp[i] is the largest. So the final state is max(dp[i]).

Code (Java):

public class Solution {
    public int longestValidParentheses(String s) {
        if (s == null || s.length() < 2) {
            return 0;
        }
        
        int[] dp = new int[s.length()];
        int maxLen = 0;
        
        for (int i = s.length() - 2; i >= 0; i--) {
            if (s.charAt(i) == '(') {
                int j = i + dp[i + 1] + 1;
                if (j < s.length() && s.charAt(j) == ')') {
                    dp[i] = dp[i + 1] + 2;
                    if (j + 1 < s.length()) {
                        dp[i] += dp[j + 1];
                    }
                }
            }
            
            maxLen = Math.max(maxLen, dp[i]);
        }
        
        return maxLen;
    }
}

Solution 2: Using a stack

public class Solution {
    public int longestValidParentheses(String s) {
        if (s == null || s.length() < 2) {
            return 0;
        }
        
        Stack<Integer> stack = new Stack<Integer>();
        int max = 0;
        int start = 0;
        
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                if (stack.isEmpty()) {
                    start = i + 1;
                } else {
                    stack.pop();
                    if (stack.isEmpty()) {
                        max = Math.max(max, i - start + 1);
                    } else {
                        max = Math.max(max, i - stack.peek());
                    }
                }
            }
        }
        
        return max;
    }
}