LeetCode. 32. Longest Valid Parentheses

On this page

[Link] https://leetcode.com/problems/longest-valid-parentheses/

Approach

Scan the string from left to right while storing character indices in an ArrayDeque<Integer>. The stack starts with the sentinel index -1, which acts as the boundary immediately before the current valid substring.

For each opening parenthesis, push its index. For each closing parenthesis, pop the most recent unmatched opening position (or the sentinel). If the stack becomes empty, the closing parenthesis has no matching opening parenthesis, so push its index as the new invalid boundary. Otherwise, the stack top is the index immediately before the valid suffix ending at the current position; its length is i - stack.peek(), so update the maximum.

The stack invariant is that, after each character is processed, its top is the boundary before the longest valid suffix ending at the current index, or the latest unmatched closing parenthesis if no such suffix exists. Opening indices below the top delimit unmatched opens; popping one on a close either reveals the boundary for a valid suffix or exposes that the current close is unmatched. The -1 sentinel handles a valid substring beginning at index zero without a separate case.

Each index is pushed and popped at most once. The time complexity is O(N) and the auxiliary space complexity is O(N), where N is the string length.

Java

import java.util.ArrayDeque;

class Solution {
    public int longestValidParentheses(String s) {
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        stack.push(-1);
        int max = 0;

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    max = Math.max(max, i - stack.peek());
                }
            }
        }
        return max;
    }
}