Longest Valid Parentheses
Asked at Meta
Problem
Given a string containing just the characters open and close parentheses, find the length of the longest valid (well-formed) parentheses substring.
Asked At
| Company | Difficulty | |
|---|---|---|
| Meta | HARD | View all Meta questions → |
How to Think About It
A brute force approach checks every possible substring and validates whether it is a well-formed parentheses string.
This is O(n^3) which is too slow for large inputs.
A stack-based approach can track indices of unmatched parentheses and compute valid lengths between them.
Use a stack initialized with -1 as a base index. Push index of open paren, pop on close paren and update max length.
A DP approach where dp[i] stores the length of the longest valid substring ending at index i can also work in O(n).
Optimal Approach
Use a stack initialized with -1 as a sentinel base index. Iterate through the string: push the index of each open parenthesis. For each close parenthesis, pop from the stack. If the stack is empty after popping, push the current index as the new base. Otherwise, update the maximum length as the difference between the current index and the new stack top. This computes the longest valid substring in O(n) time and O(n) space.
What Trips People Up in Real Interviews
Clarify what constitutes a valid parentheses substring — each open must have a matching close in the correct order.
The stack approach is the most intuitive and commonly expected in interviews.
Walk through examples to show how the stack stores indices and computes lengths.
Discuss the two-pointer alternative which achieves O(1) space but is trickier to implement.
Edge cases: all open parens, all close parens, empty string, alternating invalid pattern like ")(".
Solution Code
def longestValidParentheses(s):
stack = [-1]
max_len = 0
for i in range(len(s)):
if s[i] == '(':
stack.append(i)
else:
stack.pop()
if not stack:
stack.append(i)
else:
max_len = max(max_len, i - stack[-1])
return max_lenFrequently Asked Questions
What is the Longest Valid Parentheses problem?
Given a string containing just the characters open and close parentheses, find the length of the longest valid (well-formed) parentheses substring.
How do you solve Longest Valid Parentheses?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Longest Valid Parentheses?
Longest Valid Parentheses is asked at Meta. It is a hard difficulty problem.
What are common mistakes on Longest Valid Parentheses?
- Clarify what constitutes a valid parentheses substring — each open must have a matching close in the correct order.
- The stack approach is the most intuitive and commonly expected in interviews.
- Walk through examples to show how the stack stores indices and computes lengths.
- Discuss the two-pointer alternative which achieves O(1) space but is trickier to implement.
- Edge cases: all open parens, all close parens, empty string, alternating invalid pattern like ")(".