Find the length of the longest valid parenthesis sequence in a string, in O(n) time

Question

My friend ran into a question in an interview and he was told that there is an O(n) solution. However, neither of us can think it up. Here is the question:

There is a string which contains just ( and ), find the length of the longest valid parentheses substring, which should be well formed.

For example ")()())", the longest valid parentheses is ()() and the length is 4.

I figured it out with dynamic programming, but it is not O(n). Any ideas?

public int getLongestLen(String s) {
    if (s == null || s.length() == 0)
        return 0;

    int len = s.length(), maxLen = 0;
    boolean[][] isValid = new boolean[len][len];
    for (int l = 2; l < len; l *= 2)
        for (int start = 0; start <= len - l; start++) {
            if ((s.charAt(start) == '(' && s.charAt(start + l - 1) == ')') && 
                (l == 2 || isValid[start+1][start+l-2])) {
                    isValid[start][start+l-1] = true;
                    maxLen = Math.max(maxLen, l);
                }
        }

    return maxLen;
}

Answer 1

I did this question before, and it is not easy to come up with O(n) solution under pressure. Here is it, which is solved with stack.

   private int getLongestLenByStack(String s) {
    //use last to store the last matched index
    int len = s.length(), maxLen = 0, last = -1;
    if (len == 0 || len == 1)
        return 0;

    //use this stack to store the index of '('
    Stack<Integer> stack = new Stack<Integer>();
    for (int i = 0; i < len; i++) {
        if (s.charAt(i) == '(') 
            stack.push(i);
        else {
            //if stack is empty, it means that we already found a complete valid combo
            //update the last index.
            if (stack.isEmpty()) {
                last = i;        
            } else {
                stack.pop();
                //found a complete valid combo and calculate max length
                if (stack.isEmpty()) 
                    maxLen = Math.max(maxLen, i - last);
                else
                //calculate current max length
                    maxLen = Math.max(maxLen, i - stack.peek());
            }
        }
    }

    return maxLen;
}