public static int longestValidParentheses(String s){
  if (s == null)   return 0;
  Stack<Integer> stack=new Stack<Integer>();
  int maxLen=0;
  int len=0;
  for (int i=0; i < s.length(); i++) {
    if (s.charAt(i) == '(')     stack.push(i);
 else     if (s.isEmpty())     len=0;
 else {
      int matchedPos=stack.pop();
      int matchedLen=i - matchedPos + 1;
      if (s.isEmpty()) {
        len+=matchedLen;
        matchedLen=len;
      }
 else       matchedLen=i - stack.peek();
      maxLen=Math.max(maxLen,matchedLen);
    }
  }
  return maxLen;
}

public static int longestValidParentheses ( String s ) { if ( s == null ) return 0 ; Stack < Integer > stack = new Stack < Integer > ( ) ; int maxLen = 0 ; int len = 0 ; for ( int i = 0 ; i < s . length ( ) ; i ++ ) { if ( s . charAt ( i ) == '(' ) stack . push ( i ) ; else if ( s . isEmpty ( ) ) len = 0 ; else { int matchedPos = stack . pop ( ) ; int matchedLen = i - matchedPos + 1 ; if ( s . isEmpty ( ) ) { len += matchedLen ; matchedLen = len ; } else matchedLen = i - stack . peek ( ) ; maxLen = Math . max ( maxLen , matchedLen ) ; } } return maxLen ; }
optimized dp build a stack for indices of open parentheses traverse the string , if current is open paren , push to stack otherwise , its close paren . if stack is empty , no open paren left , reset len to 0 . if not , pop the index from stack , matchedlen = current index - index of pop open paren + 1 if stack is empty , means this matchedlen can be added to the whole len if not ,
