algorithmlanguage-agnosticdynamic-programmingcode-complexity

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


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;
}

Solution

  • 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;
    }