32. Longest Valid Parentheses

Stack

class Solution {
    public int longestValidParentheses(String s) {
        Stack<Integer> leftBracketIndexStack = new Stack<>();

        int maxLength = 0;
        int startIndex = 0; // 指向首个左括号
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                leftBracketIndexStack.push(i);
            } else {
                if (leftBracketIndexStack.isEmpty()) {
                    // 无可匹配的左括号，括号对只能从下一个字符开始
                    startIndex = i + 1;
                } else {
                    // 注意此处弹出的左括号索引不会被使用，因为以当前右括号结尾的最长有效括号子串不一定左侧为弹出的这个左括号
                    // eg: ()()
                    leftBracketIndexStack.pop();

                    if (leftBracketIndexStack.isEmpty()) {
                        // 栈中无左括号，则需要与 startIndex 进行计算。eg: ()(), 当遍历到最后一个字符时，长度应该为 4 而不是 2
                        maxLength = Math.max(maxLength, i - startIndex + 1);
                    } else {
                        // 栈中还存在左括号，注意左端点是 stack.peek() 而不是刚刚弹出的左括号索引。eg: (()(), 当遍历到最后一个字符时，长度应该为 4 而不是 2。注意不含左端点。
                        maxLength = Math.max(maxLength, i - leftBracketIndexStack.peek());
                    }
                }
            }
        }

        return maxLength;
    }
}

DP

class Solution {
    public int longestValidParentheses(String s) {
        int n = s.length();
        int maxLength = 0;

        // 定义 dp[i] 为 s 前 i 个字符组成的字符串的最长有效括号子串的长度
        int[] dp = new int[n + 1];

        for (int i = 1; i <= s.length(); i++) {
            char c = s.charAt(i - 1);
            if (c == ')') {
                // 只能以 ')' 结尾时可能组成有效括号子串

                if (i - 2 >= 0) {
                    char prev = s.charAt(i - 2);
                    if (prev == '(') {
                        // end with "()"
                        dp[i] = dp[i - 2] + 2;
                    } else {
                        // prev == ')', end with "))"
                        int subStrLength = dp[i - 1];
                        if (subStrLength > 0) {
                            int leftmostIndex = i - 1 - subStrLength - 1;
                            if (leftmostIndex >= 0 && s.charAt(leftmostIndex) == '(') {
                                dp[i] = dp[leftmostIndex] + 1 + dp[i - 1] + 1;
                            }
                        }
                    }
                }

                maxLength = Math.max(maxLength, dp[i]);
            }
        }

        return maxLength;
    }
}

Reference

32. Longest Valid Parentheses