Longest Valid Parentheses

Problem Link

32. Longest Valid Parentheses – LeetCode

Problem Statement

Given a string containing just the characters '(' and ')', return the length of the longest valid (well-formed) parentheses substring.

Examples

Example 1:

Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"

Example 2:

Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"

Example 3:

Input: s = ""
Output: 0

Constraints

• 0 <= s.length <= 3 * 10⁴

• s[i] is either '(' or ')'

Intuition

To find the longest valid parentheses substring, we need to track matching opening and closing parentheses and compute the length of valid segments.

A stack is used to store indices of unmatched '('. When we find a valid match, we compute the length based on the index at the top of the stack.

We initialize the stack with -1 to handle edge cases like "()".

Approach: Stack with Index Tracking

1. Initialize a Stack<Integer> and push -1 to serve as a base index.

2. Iterate through the string:

   • If s[i] == '(', push the index i.

   • If s[i] == ')':

     • If the stack has more than one item:

       • Pop the top (matched opening index).

       • Calculate valid length: i - stack.peek(), update maxValid.

     • If only one item is in the stack (base index or unmatched )), update base by pushing current index.

3. Return the maximum valid length.

Java Code

class Solution {
    public int longestValidParentheses(String s) {
        Stack<Integer> stack = new Stack<>();
        stack.push(-1); // base for valid substrings
        int maxValid = 0;

        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '(') {
                stack.push(i);
            } else {
                if (stack.size() > 1) {
                    stack.pop();
                    maxValid = Math.max(maxValid, i - stack.peek());
                } else {
                    // reset the base index
                    stack.pop();
                    stack.push(i);
                }
            }
        }

        return maxValid;
    }
}

Time and Space Complexity

Dry Run

Input:

s = ")()())"

Stack Trace:

Final Output:

4

Alternate Approaches

• Two Pass Without Stack (O(1) space):

  • Traverse left to right and right to left counting open/close counts.

  • Reset when unbalanced.

  • Max length tracked when counts are equal.

Conclusion

This problem is a classic use of stack-based index tracking to find longest valid matching segments.

Key techniques:

• Stack initialized with -1 to anchor base positions.

• Tracking indices, not characters, allows easy computation of lengths.