[Hard] 32. Longest Valid Parentheses

Given a string containing just the characters '(' and ')', find 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
Explanation: Empty string has no valid parentheses.

Example 4:

Input: s = "((()))"
Output: 6
Explanation: The entire string is a valid parentheses substring.

Constraints

0 <= s.length <= 3 * 10^4
s[i] is '(', or ')'.

Clarification Questions

Before diving into the solution, here are 5 important clarifications and assumptions to discuss during an interview:

Valid parentheses definition: What makes a parentheses substring valid? (Assumption: Every opening ‘(‘ has a matching closing ‘)’, properly nested)
Substring vs subsequence: Do we need a contiguous substring or can it be a subsequence? (Assumption: Substring - must be contiguous characters)
Empty string: What should we return for an empty string? (Assumption: Return 0 - no valid parentheses substring)
Character set: What characters can appear? (Assumption: Only ‘(‘ and ‘)’ - per constraints)
Return value: Should we return length or the substring itself? (Assumption: Return length - integer representing longest valid parentheses substring)

Interview Deduction Process (30 minutes)

Step 1: Brute-Force Approach (8 minutes)

Initial Thought: “I need to find longest valid substring. Let me check all possible substrings.”

Naive Solution: Check all possible substrings, for each check if valid parentheses, track maximum length.

Complexity: O(n³) time, O(n) space

Issues:

O(n³) time - very inefficient
Repeats validity checking for overlapping substrings
Doesn’t leverage stack or DP
Can be optimized significantly

Step 2: Semi-Optimized Approach (10 minutes)

Insight: “I can use stack to track valid parentheses, or use DP to track valid lengths.”

Improved Solution: Use stack to track unmatched opening parentheses. When encountering ‘)’, if stack not empty, pop and calculate length. Track maximum length.

Complexity: O(n) time, O(n) space

Improvements:

Stack naturally handles parentheses matching
O(n) time is much better
Handles all cases correctly
Can optimize further

Step 3: Optimized Solution (12 minutes)

Final Optimization: “Stack approach is optimal. Can also use DP with two passes.”

Best Solution: Stack approach is optimal. Use stack storing indices. When ‘)’, pop and calculate length from stack top (or -1 if empty). Alternative: DP with two passes (left-to-right and right-to-left).

Complexity: O(n) time, O(n) space

Key Realizations:

Stack is perfect for parentheses matching
O(n) time is optimal - single pass
Index tracking enables length calculation
DP alternative exists but stack is clearer

Solution Approaches

This problem requires finding the longest valid parentheses substring. A valid parentheses substring must have matching opening and closing parentheses.

Solution 1: Dynamic Programming

Time Complexity: O(n)
Space Complexity: O(n)

Use dynamic programming to track the length of the longest valid parentheses ending at each position.

class Solution {
public:
    int longestValidParentheses(string s) {
        int maxCount = 0;
        int len = s.length();
        vector<int> dp(len);
        
        for (int i = 1; i < len; i++) {
            if (s[i] == ')') {
                // Case 1: Pattern "()" - simple match
                if (s[i - 1] == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } 
                // Case 2: Pattern "))" - nested or consecutive valid substrings
                else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(') {
                    dp[i] = dp[i - 1] + 
                        ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                maxCount = max(maxCount, dp[i]);
            }
        }
        
        return maxCount;
    }
};

How it works:

dp[i] represents the length of the longest valid parentheses substring ending at index i
For each ')' at position i:
- Case 1: If previous character is '(', we have a simple match "()". Add 2 plus any valid substring before it.
- Case 2: If previous character is ')', check if there’s a matching '(' before the valid substring ending at i-1. If found, combine lengths.
Track the maximum length seen so far.

Solution 2: Two-Pass Greedy (Space Optimized)

Time Complexity: O(n)
Space Complexity: O(1)

Use two passes (left-to-right and right-to-left) to find the longest valid substring without extra space.

class Solution {
public:
    int longestValidParentheses(string s) {
        int left = 0, right = 0, maxLen = 0;
        int len = s.length();
        
        // Left to right pass
        for (int i = 0; i < len; i++) {
            if (s[i] == '(') left++;
            else right++;
            
            if (left == right) {
                maxLen = max(maxLen, 2 * right);
            } else if (right > left) {
                // Invalid: more closing than opening, reset
                left = right = 0;
            }
        }
        
        // Right to left pass
        left = right = 0;
        for (int i = len - 1; i >= 0; i--) {
            if (s[i] == '(') left++;
            else right++;
            
            if (left == right) {
                maxLen = max(maxLen, 2 * left);
            } else if (left > right) {
                // Invalid: more opening than closing, reset
                left = right = 0;
            }
        }
        
        return maxLen;
    }
};

How it works:

Left-to-right pass: Count opening and closing parentheses. When counts are equal, we have a valid substring. If closing > opening, reset (invalid).
Right-to-left pass: Same logic but reversed. Catches cases where left-to-right misses valid substrings (e.g., "(()").
The two passes together ensure we find all valid substrings.

How the Algorithms Work

Solution 1: Dynamic Programming Breakdown

Key Insight: dp[i] = length of longest valid parentheses substring ending at index i.

Case 1: Pattern "()"

Index:  i-2  i-1  i
String:  ?    (   )
dp:      x    0   2+x

If s[i-1] == '(' and s[i] == ')':
  dp[i] = dp[i-2] + 2

Case 2: Pattern "))"

Index:  i-dp[i-1]-2  ...  i-dp[i-1]-1  ...  i-1  i
String:      ?            (            ...   )   )
dp:          y            0            ...   x   x+y+2

If s[i-dp[i-1]-1] == '(':
  dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2

Step-by-Step Example: `s = ")()())"`

DP Solution:

s = ")()())"
    0123456

i=0: ')' → dp[0] = 0
i=1: '(' → dp[1] = 0
i=2: ')' → Case 1: s[1]=='(' → dp[2] = dp[0] + 2 = 0 + 2 = 2
i=3: '(' → dp[3] = 0
i=4: ')' → Case 1: s[3]=='(' → dp[4] = dp[2] + 2 = 2 + 2 = 4
i=5: ')' → Case 2: Check s[5-dp[4]-1] = s[0] = ')' → No match
           dp[5] = 0

maxCount = max(0, 0, 2, 0, 4, 0) = 4

Two-Pass Solution:

Left-to-right: ")()())"
i=0: ')' → left=0, right=1 → right>left → reset → left=0, right=0
i=1: '(' → left=1, right=0
i=2: ')' → left=1, right=1 → equal → maxLen = max(0, 2*1) = 2
i=3: '(' → left=2, right=1
i=4: ')' → left=2, right=2 → equal → maxLen = max(2, 2*2) = 4
i=5: ')' → left=2, right=3 → right>left → reset → left=0, right=0

Right-to-left: ")()())"
i=5: ')' → left=0, right=1
i=4: ')' → left=0, right=2 → right>left → reset → left=0, right=0
i=3: '(' → left=1, right=0
i=2: ')' → left=1, right=1 → equal → maxLen = max(4, 2*1) = 4
i=1: '(' → left=2, right=1 → left>right → reset → left=0, right=0
i=0: ')' → left=0, right=1

Final: maxLen = 4

Step-by-Step Example: `s = "(()"`

DP Solution:

s = "(()"
    012

i=0: '(' → dp[0] = 0
i=1: '(' → dp[1] = 0
i=2: ')' → Case 2: Check s[2-dp[1]-1] = s[1] = '(' → Match!
           dp[2] = dp[1] + dp[2-dp[1]-2] + 2
                 = 0 + dp[-1] + 2
                 = 0 + 0 + 2 = 2

maxCount = 2

Two-Pass Solution:

Left-to-right: "(()"
i=0: '(' → left=1, right=0
i=1: '(' → left=2, right=0
i=2: ')' → left=2, right=1 → left>right → continue
maxLen = 0 (no equal counts)

Right-to-left: "(()"
i=2: ')' → left=0, right=1
i=1: '(' → left=1, right=1 → equal → maxLen = max(0, 2*1) = 2
i=0: '(' → left=2, right=1 → left>right → reset

Final: maxLen = 2

Algorithm Breakdown

Solution 1: Dynamic Programming

Base Case:

dp[0] = 0 (no valid substring ending at index 0 if it’s not part of a match)

Case 1: Simple Match "()"

if (s[i - 1] == '(') {
    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
}

If previous character is '(', we have a match
Add 2 for the current match
Add any valid substring before i-2

Case 2: Nested/Consecutive "))"

else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(') {
    dp[i] = dp[i - 1] + 
        ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
}

Check if there’s a matching '(' before the valid substring ending at i-1
If found, combine:
- Length of valid substring ending at i-1: dp[i-1]
- Length of valid substring before the match: dp[i-dp[i-1]-2]
- Current match: 2

Solution 2: Two-Pass Greedy

Left-to-Right Pass:

for (int i = 0; i < len; i++) {
    if (s[i] == '(') left++;
    else right++;
    
    if (left == right) {
        maxLen = max(maxLen, 2 * right);
    } else if (right > left) {
        left = right = 0;  // Reset: invalid state
    }
}

Count opening and closing parentheses
When equal, we have a valid substring
If closing > opening, reset (can’t form valid substring)

Right-to-Left Pass:

for (int i = len - 1; i >= 0; i--) {
    if (s[i] == '(') left++;
    else right++;
    
    if (left == right) {
        maxLen = max(maxLen, 2 * left);
    } else if (left > right) {
        left = right = 0;  // Reset: invalid state
    }
}

Same logic but reversed
Catches cases where left-to-right misses valid substrings

Why Two Passes?

Left-to-right misses cases like "(()" where we never get left == right
Right-to-left catches these cases
Together, they find all valid substrings

Complexity Analysis

Approach	Time	Space	Pros	Cons
Dynamic Programming	O(n)	O(n)	Clear logic, handles all cases	Extra space
Two-Pass Greedy	O(n)	O(1)	Optimal space, simple	Two passes needed

Edge Cases

Empty string: Returns 0
No valid parentheses: Returns 0 (e.g., "))" or "((")
All valid: Returns string length (e.g., "()()()")
Nested valid: Returns string length (e.g., "((()))")
Single character: Returns 0 (no pair possible)

Key Insights

DP State Definition: dp[i] = longest valid substring ending at i
Two Cases: Simple match "()" and nested/consecutive "))"
Greedy Approach: Count parentheses and reset when invalid
Two Passes: Needed to catch all valid substrings

Common Mistakes

Missing Case 2 in DP: Forgetting to handle nested/consecutive valid substrings
Index Out of Bounds: Not checking i - dp[i-1] > 0 before accessing
Single Pass Greedy: Missing valid substrings that don’t balance in one direction
Wrong Reset Condition: Resetting at wrong times in greedy approach

Alternative Approaches

Approach 3: Stack-Based

Time Complexity: O(n)
Space Complexity: O(n)

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> stk;
        stk.push(-1);  // Base for calculation
        int maxLen = 0;
        
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == '(') {
                stk.push(i);
            } else {
                stk.pop();
                if (stk.empty()) {
                    stk.push(i);  // New base
                } else {
                    maxLen = max(maxLen, i - stk.top());
                }
            }
        }
        
        return maxLen;
    }
};

How it works:

Use stack to track indices of unmatched '('
When ')' is found, pop and calculate length
If stack is empty after pop, push current index as new base

20. Valid Parentheses - Check if entire string is valid
22. Generate Parentheses - Generate all valid combinations
301. Remove Invalid Parentheses - Remove minimum to make valid
921. Minimum Add to Make Parentheses Valid - Minimum additions needed

Pattern Recognition

This problem demonstrates:

Dynamic Programming with String Matching: Building solution incrementally
Greedy with Two Passes: Ensuring all cases are covered
Parentheses Matching: Classic pattern in string problems

Real-World Applications

Code Parsing: Validating syntax in compilers
Expression Evaluation: Checking balanced expressions
Text Processing: Finding well-formed structures
Algorithm Design: Understanding DP and greedy patterns

Why Two Solutions?

Use DP when:

Need to understand the problem structure clearly
Want to see all intermediate results
Space is not a concern

Use Two-Pass Greedy when:

Space is constrained
Need O(1) space solution
Want simpler code (though requires two passes)

This problem demonstrates both dynamic programming and greedy approaches to solve the same problem, with different space-time trade-offs.

Robina Li

[Hard] 32. Longest Valid Parentheses

[Hard] 32. Longest Valid Parentheses

Examples

Constraints

Clarification Questions

Interview Deduction Process (30 minutes)

Step 1: Brute-Force Approach (8 minutes)

Step 2: Semi-Optimized Approach (10 minutes)

Step 3: Optimized Solution (12 minutes)

Solution Approaches

Solution 1: Dynamic Programming

Solution 2: Two-Pass Greedy (Space Optimized)

How the Algorithms Work

Solution 1: Dynamic Programming Breakdown

Step-by-Step Example: `s = ")()())"`

Step-by-Step Example: `s = "(()"`

Algorithm Breakdown

Solution 1: Dynamic Programming

Solution 2: Two-Pass Greedy

Complexity Analysis

Edge Cases

Key Insights

Common Mistakes

Alternative Approaches

Approach 3: Stack-Based

Pattern Recognition

Real-World Applications

Why Two Solutions?

Related Posts

Recent Posts

[Hard] 32. Longest Valid Parentheses

Examples

Constraints

Clarification Questions

Interview Deduction Process (30 minutes)

Step 1: Brute-Force Approach (8 minutes)

Step 2: Semi-Optimized Approach (10 minutes)

Step 3: Optimized Solution (12 minutes)

Solution Approaches

Solution 1: Dynamic Programming

Solution 2: Two-Pass Greedy (Space Optimized)

How the Algorithms Work

Solution 1: Dynamic Programming Breakdown

Step-by-Step Example: s = ")()())"

Step-by-Step Example: s = "(()"

Algorithm Breakdown

Solution 1: Dynamic Programming

Solution 2: Two-Pass Greedy

Complexity Analysis

Edge Cases

Key Insights

Common Mistakes

Alternative Approaches

Approach 3: Stack-Based

Related Problems

Pattern Recognition

Real-World Applications

Why Two Solutions?

Related Posts

Recent Posts

Step-by-Step Example: `s = ")()())"`

Step-by-Step Example: `s = "(()"`