Longest Valid Parentheses

There is the longest valid parentheses problem definition.

We are given a string containing just parentheses of character ')' and '(' only, find the length of the longest valid (well-formed) parentheses substring. For example, for "(()", the longest valid parentheses substring is "()", output is 2. Anther example is ")()())", the longest valid parentheses substring is "()()", which has length of 4.

Approach I: dynamic programming

As usual many of the string related problems can be solved by dynamic problem. Given a substring from index at i to j, how can we find out the longest valid parentheses substring, which is not easy to construct the dynamic function. But we can convert this problem to another problem, that is, given substring S from index i to j, find out if all of the parentheses in the substring S form valid pair.

Here is how we construct isValid dynamic function based on index i and j, which is to break the substring(i,j) to two part: i,k and k+1, j. in which k = i+1, i+3, i+5, ..., j-2.

if(isValid(i,k) && isValid(k+1,j)) then isValid(i,j) = true.

Here is the java code:

public static int longestValidParentheses(String str){
int len = str.length();
boolean[][] isValid = new boolean[len][len];
int maxLen = 0;
for(int i =0; i< len-1; i++){
if(str.charAt(i)=='(' && str.charAt(i+1) == ')'){
isValid[i][i+1] = true;
maxLen = 2;
}
}

for(int step=3; step<len; step=step+2){ for(int i=0; i+step<len; i++){ int j = i+step;
if(isValid[i+1][j-1]&&isValid(str,i,j)) isValid[i][j] = true; for(int k=i+1; k<=j-2; k=k+2){ if(isValid[i][k] && isValid[k+1][j]) isValid[i][j] = true; if(isValid[i][j]){ maxLen = Math.max(maxLen, j - i + 1); break; } } } }
return maxLen;
}

private static boolean isValid(String str, int i, int j){
return str.charAt(i) == '(' && str.charAt(j) == ')';
}

Approach II: using stack

Stack is great data structure, the difference between stack and queue is that you update and query from the same place: the back, while in queue you have two places to update: insert at back, remove at front. That is the reason we can use stack is constructed data structure like max/min stack and max/min queue, in this case, the queue is built on top of stack, as well.

static class Node {
        int pos;
        char c;
        Node(int p, char c){
            this.pos = p;
            this.c = c;
        }
    }
    public static int maxValidParenthesis(String input){
        int max = 0;
        Stack<Node> s = new Stack<Node>();
        for(int i=0, j= input.length(); i<j; i++){
            char c = input.charAt(i);
            if(s.isEmpty() || c == '(' || s.peek().c == ')')
                s.push(new Node(i, c));
            else{
                s.pop();
                max = Math.max(i - (s.isEmpty()?-1:s.peek().pos), max);
            }
        }
        return max;
    }