[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.

Solution1: O(n)

public class Solution {
    public int longestValidParentheses(String s) {
        Stack stack = new Stack();
        int i    = 0;
        int last = -1;
        int max  = 0;
        
        while(i < s.length()) {
            if(s.charAt(i) == '(') {
                stack.push(i);
            } else {
                if(stack.empty()) {
                    last = i;
                } else {
                    stack.pop();
                    if(stack.empty()) {
                        max = Math.max(max, i - last);
                    } else {
                        max = Math.max(max, i - stack.peek());
                    }
                }
            }
            i++;
        }
        return max;
    }
}


Solution 2: O(n), Using DP


public class Solution {
    public int longestValidParentheses(String s) {
        if(s == null || s.length()<2 )
            return 0;
        
        int f[] = new int[s.length()];
        int max = 0;
        for(int i=1; i<s.length();i++){
            if(s.charAt(i) == ')' ){
                if(s.charAt(i-1) == '('){
                    if(i < 2)
                        f[i] = 2;
                    else    
                        f[i] = f[i-2] +2;
                }else if(f[i-1] >0){
                    int p = i - f[i-1] -1;
                    if(p>=0 && s.charAt(p) == '(' ){
                        f[i] = f[i-1] +2;
                        if(p>1)
                          f[i]+= f[p-1];
                    }
               }
            }
            max = Math.max(max,f[i]);
        }
        return max;
    }
}
Key Concept: We can use DP to solve this problem as well as using stack 
to store most left "(" position