Cacher is the code snippet organizer for pro developers

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

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

public class Solution {
    public int longestValidParentheses(String s) {
        
      char[] S = s.toCharArray();
        int [] DP = new int [S.length];
        int max = 0;
        for (int i=1; i< S.length; i++) {
            if (S[i] == ')') {
                int j=i-1-DP[i-1];
                if (j>=0 && S[j] == '(') {
                    DP[i] = 2+DP[i-1]+(j>0? DP[j-1]:0);
                }
            }
        max = Math.max(max, DP[i]);
        }
        
       return max;
    }
}

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