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.

Solution

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

        Stack<Integer> stack = new Stack<>();
        int ret = 0;
        int prev = -1;
        for(int i = 0; i < s.length(); i ++) {
            char currentChar = s.charAt(i);

            if(currentChar == '(') {
                stack.push(i);
            } else if(currentChar == ')') {
                if(!stack.isEmpty()) {
                    stack.pop();

                    if(stack.isEmpty()) {
                        ret = Math.max(ret, i - prev);
                    } else {
                        ret = Math.max(ret, i - stack.peek());
                    }
                } else {
                    prev = i;
                }
            }
        }

        return ret;
    }

}