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!