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):

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

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

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

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;     } }