Cacher is the code snippet organizer for pro developers

/**
 * 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.
 */

public class Solution {
    public int longestValidParentheses(String s) {
        int maxLen = 0, startFrom = -1;
        Stack<Integer> lefts = new Stack<Integer>();
        for(int i = 0; i < s.length(); i++){
            // if it is open
            if(s.charAt(i) == '(')
                lefts.push(i);
            else{
                if(lefts.isEmpty()){
                    // no matching
                    startFrom = i;
                }else{
                    // find a matching pair;
                    lefts.pop();
                    if(lefts.isEmpty()){
                        maxLen = Math.max(maxLen, i - startFrom);
                    }else{
                        maxLen = Math.max(maxLen, i - lefts.peek());
                    }
                }
            }
        }
        return maxLen;
    }
    
    // DP solution
    public int longestValidParentheses(String s) {
        if (s == null || "".equals(s)) return 0;
        int[] dp = new int[s.length() + 1];
        int max = 0;
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == ')' && i - dp[i] >= 1 && s.charAt(i - dp[i] - 1) == '(') {
                dp[i + 1] = dp[i - dp[i] - 1] + dp[i] + 2;
            }
        }
        for (int i = 0; i < dp.length; i++) {
            if (dp[i] > max) max = dp[i];
        }
        return max;
    }
}