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.

Analysis

• Initialize a stack of Integer to put index
• append 'x' to string (必须append一个x到s后面，如果不append，碰到"(()"的情况，最后一个')'加进去的时候不update max)
• Scan each char in String s
  • if char==')' && !stack.isEmpty() && char at stack.peek() is '(' {stack pop}
  • else
    • if (stack.isEmpty()) {max: i}
    • else {max: i-stack.peek()-1}
    • push(i)
• return max

Code

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

Reference

Leetcode: 3rd code