LeetCode 32: Longest Valid Parentheses Solution in Python Explained

Problem Statement

LeetCode 32, Longest Valid Parentheses, is a hard-level problem where you’re given a string s containing only parentheses (( and )). Your task is to find the length of the longest valid (well-formed) substring of parentheses. A substring is valid if every opening parenthesis ( has a matching closing parenthesis ).

Constraints

0 <= s.length <= 3 * 10^4: String length is between 0 and 30,000.
s[i] is either ( or ).

Example

Input: s = "(()"
Output: 2
Explanation: Longest valid substring is "()", length 2.

Input: s = ")()())"
Output: 4
Explanation: Longest valid substring is "()()", length 4.

Input: s = ""
Output: 0
Explanation: Empty string has no valid parentheses.

Understanding the Problem

How do you solve LeetCode 32: Longest Valid Parentheses in Python? For s = ")()())", the longest valid substring is "()()" (length 4), not just "()" (length 2). We need to track matching pairs across the string. We’ll explore two approaches: a Stack-Based Solution (optimal and primary) and an Alternative with Dynamic Programming (intuitive but more complex). The stack method efficiently tracks unmatched parentheses to compute valid lengths.

Solution 1: Stack-Based Approach (Primary)

Explanation

Use a stack to track indices of unmatched parentheses. Push indices of ( onto the stack, pop when encountering ), and calculate the length of valid substrings using the stack’s top or start point. If the stack is empty after popping, use the last unmatched position as the base.

Here’s a visual for s = ")()())":

Stack: [-1] -> [-1,1] -> [-1] -> [-1,3] -> [-1] -> []
Lengths: 0, 2 (1-(-1)), 4 (3-(-1))

Initialize Stack.

Start with -1 as a base index.

Process String.

Push ( indices, pop for ), compute length.

Track Maximum Length.

Update max when valid substring found.

Step-by-Step Example

Example 1: s = ")()())"

We need length 4.

Goal: Find longest valid substring.
Result for Reference: 4.
Start: s = ")()())", stack = [-1].
Step 1: i = 0, ")" – no match, push 0, stack = [-1,0].
Step 2: i = 1, "(" – push 1, stack = [-1,0,1].
Step 3: i = 2, ")" – pop 1, stack = [-1,0], length = 2-0 = 2, max_len = 2.
Step 4: i = 3, "(" – push 3, stack = [-1,0,3].
Step 5: i = 4, ")" – pop 3, stack = [-1,0], length = 4-0 = 4, max_len = 4.
Step 6: i = 5, ")" – no match, push 5, stack = [-1,0,5].
Finish: max_len = 4.

Example 2: s = "(()"

We need length 2.

Goal: Longest valid substring.
Result for Reference: 2.
Start: stack = [-1].
Step 1: i = 0, "(" – push 0, stack = [-1,0].
Step 2: i = 1, "(" – push 1, stack = [-1,0,1].
Step 3: i = 2, ")" – pop 1, stack = [-1,0], length = 2-0 = 2.
Finish: max_len = 2.

How the Code Works (Stack-Based)

Here’s the Python code with line-by-line explanation:

def longestValidParentheses(s: str) -> int:
    # Line 1: Initialize stack with base index
    stack = [-1]
    max_len = 0

    # Line 2: Process each character
    for i in range(len(s)):
        # Line 3: If opening parenthesis
        if s[i] == '(':
            # Line 4: Push index
            stack.append(i)
        else:
            # Line 5: Pop last opening parenthesis
            stack.pop()
            # Line 6: If stack not empty, compute length
            if stack:
                max_len = max(max_len, i - stack[-1])
            else:
                # Line 7: Reset base index
                stack.append(i)

    # Line 8: Return longest valid length
    return max_len

Alternative: Dynamic Programming Approach

Explanation

Use a DP array where dp[i] is the length of the longest valid substring ending at index i. Update based on whether ) matches a previous ( and extends prior valid substrings.

Initialize DP Array.
Process String.

For ), check pairing with ( and extend.

3. Track Maximum.

Step-by-Step Example (Alternative)

For s = ")()())":

Goal: Length 4.
Start: dp = [0,0,0,0,0,0].
Step 1: i = 0, ")" – dp[0] = 0.
Step 2: i = 1, "(" – dp[1] = 0.
Step 3: i = 2, ")" – matches i-1, dp[2] = 2.
Step 4: i = 3, "(" – dp[3] = 0.
Step 5: i = 4, ")" – matches i-1, dp[4] = 2.
Step 6: i = 5, ")" – no direct match, but dp[4] = 2, check i-3, dp[5] = 4.
Finish: max(dp) = 4.

How the Code Works (DP)

def longestValidParenthesesDP(s: str) -> int:
    # Line 1: Initialize DP array
    n = len(s)
    dp = [0] * n
    max_len = 0

    # Line 2: Process from left to right
    for i in range(1, n):
        # Line 3: If closing parenthesis
        if s[i] == ')':
            # Line 4: Check if matches previous opening
            if s[i-1] == '(':
                dp[i] = 2 + (dp[i-2] if i >= 2 else 0)
            # Line 5: Check if matches earlier opening
            elif i - dp[i-1] - 1 >= 0 and s[i - dp[i-1] - 1] == '(':
                dp[i] = dp[i-1] + 2 + (dp[i - dp[i-1] - 2] if i - dp[i-1] - 2 >= 0 else 0)
            # Line 6: Update max length
            max_len = max(max_len, dp[i])

    # Line 7: Return result
    return max_len

Complexity

Stack-Based:

Time: O(n) – Single pass through string.
Space: O(n) – Stack size up to n.

Dynamic Programming:

Time: O(n) – Single pass.
Space: O(n) – DP array.

Efficiency Notes

Both are O(n) time, but Stack-Based uses O(n) space with simpler logic, making it preferred for LeetCode 32. DP is more complex but avoids stack overhead.

Key Insights

Tips to master LeetCode 32:

Stack Tracks Boundaries: Use indices, not just counts.
Base Index Trick: -1 helps compute lengths easily.
Look Beyond Pairs: Combine valid substrings for max length.

Additional Example

For s = "(())":

Goal: Length 4.
Stack: [-1,0,1] -> [-1,0] -> [-1], length 4.
Result: 4.

Edge Cases

Empty String: "" – Return 0.
No Valid Pairs: ")(" – Return 0.
All Valid: "()()" – Return 4.

Final Thoughts

The Stack-Based solution is a standout for LeetCode 32 in Python—intuitive, efficient, and perfect for this hard problem. For a related challenge, try LeetCode 31: Next Permutation to flex your array skills! Ready to conquer it? Solve LeetCode 32 on LeetCode now and test it with strings like "()(()" or "(()()" to sharpen your parentheses prowess. Dive in and tackle the challenge!