Longest Valid Parentheses

This is a hard problem. At first we have the following observations:

1. If we meet a ) without matching ( in the left, then all sub sequence contains it won't be valid, so we can regard string after that character as a independent sub problem.
2. If we can find a match, then the sub sequence from last unmatched ( to current ) will be a sub sequence contains valid parentheses.

We can use a stack to store the position of left parentheses:

public class LongestValidParentheses {
    public int longestValidParentheses(String s) {
        Stack<Integer> stack = new Stack<Integer>();

        int max = 0;
        int left = -1;

        for (int i = 0;i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '(') stack.push(i);
            else {
                if (stack.isEmpty()) {
                    left = i;
                } else {
                    stack.pop();
                    if (stack.isEmpty()) max = Math.max(max, i - left);
                    else max = Math.max(max, i - stack.peek());
                }
            }
        }


        return max;
    }
}

To save space, we can also make use of the array to simulate a stack:

public class LongestValidParentheses {
    public int longestValidParentheses(String s) {
        int left = -1, l = -1, max = 0;
        char[] str = s.toCharArray();

        for (int i = 0; i < str.length; i++) {
            if (str[i] == '(') {
                l = i;
            } else {
                if (l == left) {
                    left = i;
                    l = i;
                } else {
                    str[l--] = '.';
                    while(l > left && str[l] != '(') l--;
                    max = Math.max(max, i - l);
                }
            }
        }

        return max;
    }
}