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

The char that makes the string invalid parentheses will cut the string into parts that either is valid parentheses or empty. use a stack to process the string, then the stack is empty, while met ')', calculate the size.

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

        return max;
    }
}