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.

Update 2016-11-06

An easier to understand solution. We still use stack, which is used for those unfortunate-hasn't-been-matched parenthesis. When we see a ")", we check if the stack contains a matching "(", if there has such "(". We pop it out. If then the stack is empty, we know all previous parentheses are matched, result should be current ")"'s index + 1. Otherwise, result should be the maximum between result and current index - stack.peek(). If we cannot find a matching ")" or if it's a "(", we push the index into the stack.

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

Nothing special. Use a stack to store all the '(' positions, and pop out them when ')' comes. Track the accumulated length and take the maximum.

Update some note:
AccumulatedLength can only be incremented when the stack is empty. It is only used for cases such as "()()".  The maxLen is calculated by taking maximum between maxLen and matchedLength. Thus after we increment accumulatedLengh, we need to reassign matchedLength.

In the case like "(()()", we need to calculate the matched length by i - stack.peek(). See comment.

public class LongestParentheses {
    public int longestValidParentheses(String s) {
        if (s == null)
            return 0;
        int maxLen = 0;
        int accumulatedLength = 0;
        Stack stack = new Stack();
        for (int i = 0; i < s.length(); i++)
        {
            if (s.charAt(i) == '(')
                stack.push(i);
            else
            {
                if (stack.isEmpty())
                {
                    accumulatedLength = 0;
                    continue;
                }
                 // for case "(())"
                int matchedPos = stack.pop();
                int matchedLen = i - matchedPos + 1;
                if (stack.isEmpty())
                {
                    //for case "()()"
                    accumulatedLength += matchedLen;
                    matchedLen = accumulatedLength;
                }
                //Accumulated length will not increment if the stack
                //is not empty, thus we need to recalculate the
                //matched length to account for accumulated length
                //e.g., "(()()", i = 4, stack is not empty, the
                //accumulated length = 0, matchedLen = 4 - 0 = 4
                //in the case of "(())", we cannot increment 
                //accumulate length when i = 2, otherwise we will 
                //double count the inner parentheses
                else
                    // for case "(()()"
                    matchedLen = i - stack.peek();
                maxLen = Math.max(maxLen, matchedLen);
            }
            
        }
        return maxLen;
    }
}