How to Solve Longest Valid Parentheses

The Longest Valid Parentheses problem requires identifying contiguous valid pairs in a string of '(' and ')'. Using state transition dynamic programming, you track valid lengths ending at each index, while a stack can mark unmatched positions to guide accumulation. This approach efficiently calculates the maximum valid substring without redundant checks, combining both memory-efficient tracking and pattern-specific validation in one pass for reliable results.

Problem Statement

Given a string composed exclusively of '(' and ')', determine the length of the longest contiguous substring that forms valid parentheses. Valid parentheses must be properly nested and closed, so any substring counted cannot contain unmatched or misordered parentheses. The input string may be empty or contain a mixture of paired and unpaired parentheses.

Your task is to implement a method that returns an integer representing the maximum length of such valid substrings. For instance, for the input ")()())", the function should return 4 corresponding to the substring "()()". Ensure your solution handles edge cases where no valid parentheses exist or the string is empty, and consider using dynamic programming or a stack-based state transition approach for efficient computation.

Examples

Example 1

Input: s = "(()"

Output: 2

The longest valid parentheses substring is "()".

Example 2

Input: s = ")()())"

Output: 4

The longest valid parentheses substring is "()()".

Example 3

Input: s = ""

Output: 0

Example details omitted.

Constraints

• 0 <= s.length <= 3 * 104
• s[i] is '(', or ')'.

Solution Approach

Dynamic Programming Tracking

Use a DP array where each index stores the length of the longest valid substring ending at that position. Iterate through the string, updating the DP value when encountering a closing parenthesis that matches an earlier opening parenthesis. Handle nested and consecutive pairs by referencing previous DP entries, effectively accumulating valid substring lengths. This approach guarantees that each character is considered exactly once for state updates, capturing overlapping and nested structures systematically while maintaining linear time processing.

Stack-Based Position Tracking

Maintain a stack to store indices of unmatched opening parentheses and a base index for unmatched closing parentheses. When a closing parenthesis is found, pop the stack if it matches, then calculate the current valid length from the current index minus the new stack top. This method ensures that you correctly capture valid substring lengths even in the presence of unbalanced parentheses. It avoids recomputation by only focusing on transitions caused by closing parentheses and gives a clear mapping between stack operations and valid substring endpoints.

Combined Scan with Counters

Perform two linear scans: left-to-right and right-to-left, counting opening and closing parentheses. Whenever the counts match, update the maximum length of valid parentheses. Reset counters if closing exceeds opening in the forward pass or opening exceeds closing in the backward pass. This method uses constant space while implicitly applying the state transition principle by tracking accumulative matches. It efficiently captures edge cases where initial or trailing characters prevent full substring formation and avoids unnecessary stack or array memory usage.

Complexity Analysis

The time complexity is O(n) since each character is processed once in either the DP, stack, or counter approaches, and space complexity ranges from O(1) with counters to O(n) for DP or stack storage. This ensures linear performance while accounting for nested and overlapping parentheses structures efficiently.

What Interviewers Usually Probe

• Do you correctly handle nested valid parentheses sequences with state transition logic?
• Can you optimize space usage by choosing between DP, stack, or two-counter scans?
• Will you update your DP or stack state properly when encountering consecutive valid pairs?

Common Pitfalls or Variants

Common pitfalls

• Incorrectly counting overlapping or nested substrings, leading to underestimating maximum length.
• Failing to handle unmatched closing parentheses, causing index errors or incorrect resets.
• Using only one-directional scan without accounting for trailing unmatched opening parentheses.

Follow-up variants

• Return the actual longest valid parentheses substring instead of just its length.
• Count the total number of distinct valid parentheses substrings in the string.
• Allow additional characters beyond '(' and ')', requiring filtering or adjusted DP rules.

How GhostInterview Helps

• Capture the input string and show intermediate DP or stack states as screenshots for analysis.
• Provide step-by-step answer path including DP or stack updates, with explicit time and space complexity explanations.
• Support screen-share workflows showing stack or DP layer overlays for live debugging and substring visualization.

Topic Pages

• String
• Dynamic Programming
• Stack

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the main idea behind the DP approach for Longest Valid Parentheses?

The DP approach stores the length of the longest valid substring ending at each index, updating when a closing parenthesis matches an opening one, efficiently accumulating nested or consecutive valid lengths.

How does the stack-based method handle unmatched parentheses?

The stack keeps indices of unmatched opening parentheses, and a base index tracks unmatched closing ones. Popping and length calculations occur only when a matching closing parenthesis is found, ensuring accurate maximum lengths.

Why perform two passes with counters in this problem?

Two linear scans, left-to-right and right-to-left, allow counting matched pairs while resetting counters when mismatches occur, ensuring that edge cases with unmatched starting or trailing parentheses are correctly measured.

Can this problem be solved with O(1) extra space?

Yes, using the two-pass counter method requires only a few integer counters, achieving O(1) space while still accurately computing the maximum length of valid parentheses substrings.

What is a common mistake when implementing state transition DP here?

A frequent error is failing to reference the DP entry before the matching opening parenthesis correctly, which undercounts nested or consecutive valid sequences, leading to incorrect maximum length results.