Longest Valid Parentheses

Source

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 
length = 2.

Another example is ")()())", where the longest valid parentheses substring
is "()()", which has length = 4.

题解

To detect a valid parentheses substring, we use a stack to maintain left parentheses: Each time when hitting a '(', push its index to the stack. Each time when hitting a ')', If the stack is not empty, i.e. there is a matching '(' for it, pop the match out of the stack. At this time, we know it is an end of a valid parentheses substring. Calculate the length of the current substring and compare it with the longest we've got. If the stack is empty, there is no matching '(' for it. Move on to next character. The tricky part is how to calculate the length of the "current substring". E.g. to differentiate "()(()" and "(()()", or "())()" and ")()()".

We need to track the position where the current substring started. For case one, "()(()" and "(()()", the extra '(' must be in stack. So, after pop up a matching '(', the next top of the stack is right before the start position of the current substring. For case two, "())()" and ")()()", we need to keep track of the last invalid ')'.

Java

public class Solution {
    public int longestValidParentheses(String s) {  
        int maxLen = 0, last = -1;  
        Stack<Integer> lefts = new Stack<Integer>();  

        for (int i=0; i < s.length(); ++i) {  
            if (s.charAt(i)=='(') {  
                lefts.push(i);  
            }   
            else {  
                if (lefts.isEmpty()) {  
                    // no matching left  
                    last = i;  
                }   
                else {  
                    // find a matching pair  
                    lefts.pop();  
                    if (lefts.isEmpty()) {  
                        maxLen = Math.max(maxLen, i-last);  
                    }   
                    else {  
                        maxLen = Math.max(maxLen, i-lefts.peek());  
                    }  
                }  
            }  
        }  
        return maxLen;  
    }  
}