Longest Valid Parentheses - leetcode

longestValidParentheses.java

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

Algorithm time complexity is O(n), and space complexity is O(n)
Basic algrithm is to keep track of the longest matched paramthesis.
But we need to separate the valid substring, which have 2 special cases: ())()() and ()()(((), and others(whole string 
is valid) are easy.

case 1: use the last variable to store the last ) pos when stack is empty
case 2: compare the max with the cur pos - the top position of (
*/
public class Solution {
    public int longestValidParentheses(String s) {
        // Using stack to store the position of '('
        Stack<Integer> stack = new Stack<Integer>();
        int i    = 0;
        int last = -1;
        int max  = 0;
        
        while(i < s.length()) {
            if(s.charAt(i) == '(') {
                // push it to the stack
                stack.push(i);
            } else {
                if(stack.empty()) {
                    // last will save the pos of last ')' when stack is empty
                    last = i;
                } else {
                    stack.pop();
                    if(stack.empty()) {
                        // deal with cases when s is ())()()
                        max = Math.max(max, i - last);
                    } else {
                        // deal with cases when s is ()()(((()
                        max = Math.max(max, i - stack.peek());
                    }
                }
            }
            i++;
        }
        return max;
    }
}