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.

Solution:

parentheses?? --> stack
Each ")" needs to have to "(" to match. So we put "(" into the stack and then pop out one when there is a ")".
Case1: there are multiple "("s in the stack, waiting to be match. We just keep matching and update the longest valid parentheses.
Case2: there is only one "(" in the stack, and the length would be "last break point" to i.
Case3: there is no "(" in the stack to match, we update the "last break point" for future use.

public class Solution {
    public int longestValidParentheses(String s) {
        int last = -1;
        int maxLen = 0;
        Stack stack = new Stack();
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == '('){
                stack.push(i);
            }
            else{
                if(stack.isEmpty()) {last = i;}  // "())", stack is empty
                else{
                    stack.pop();
                    if(stack.isEmpty()) maxLen = Math.max(maxLen, i - last); // "()()" , stack has only one left parentheses
                    else maxLen = Math.max(maxLen, i - stack.peek());      // "(()()"  , two/more
                }
            }
        }
        return maxLen;
    }
}