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.

Java Solution

A stack can be used to track and reduce pairs. Since the problem asks for length, we can put the index into the stack along with the character. For coding simplicity purpose, we can use 0 to represent ( and 1 to represent ).

This problem is similar to Valid Parentheses, which can also be solved by using a stack.

public int longestValidParentheses(String s) {
    Stack<int[]> stack = new Stack<>();
    int result = 0;
 
    for(int i=0; i<s.length(); i++){
        char c = s.charAt(i);
        if(c==')'){
            if(!stack.isEmpty() && stack.peek()[0]==0){
                stack.pop();
                result = Math.max(result, i-(stack.isEmpty()?-1:stack.peek()[1]));
            }else{
                stack.push(new int[]{1, i});
            }
        }else{
            stack.push(new int[]{0, i});
        }
    }
 
    return result;
}