32. Longest Valid Parentheses

Problem:

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Example 1:

Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"

Example 2:

Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"

6/26/2018 update:
res = Math.max(res, i - stack.peek()) is the case: "(())", when i reaches the first ).
----------------------------------------------------------------------------------------------------------------------------
Analysis:

Use stack, stack only stores the index of left parentheses.
The stack top is always the pair left parentheses of its right par.
We keep updating the start of valid parentheses when there is no more left parentheses in the stack.

"(()":

input	stack	start	len
(,0	0	-1
( ,1	1, 0	-1
), 2	0	-1	2

“)()())”

input	stack	start	len
),0		0	1
(,1	1	0
), 2		0	2
(, 3	3	0
), 4		0	4
), 5		5

Solution:
If ) is met, and there are extra (, we can calc the new valid length by i - stack.peek(). Because the stack top is one position before the paired (.

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