Longest Valid Parentheses

Problem Description

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

Jump to Solution: Python Java C++ JavaScript C#

Python Solution


def longestValidParentheses(s: str) -> int:
    n = len(s)
    if n < 2:
        return 0
        
    # Dynamic programming approach
    dp = [0] * n
    max_length = 0
    
    for i in range(1, n):
        if s[i] == ')':
            # Case 1: ()
            if s[i-1] == '(':
                dp[i] = (dp[i-2] if i >= 2 else 0) + 2
            # Case 2: ))
            elif i - dp[i-1] > 0 and s[i - dp[i-1] - 1] == '(':
                dp[i] = dp[i-1] + 2
                if i - dp[i-1] >= 2:
                    dp[i] += dp[i - dp[i-1] - 2]
                    
            max_length = max(max_length, dp[i])
    
    return max_length

Java Solution


class Solution {
    public int longestValidParentheses(String s) {
        int n = s.length();
        if (n < 2) {
            return 0;
        }
        
        // Dynamic programming approach
        int[] dp = new int[n];
        int maxLength = 0;
        
        for (int i = 1; i < n; i++) {
            if (s.charAt(i) == ')') {
                // Case 1: ()
                if (s.charAt(i-1) == '(') {
                    dp[i] = (i >= 2 ? dp[i-2] : 0) + 2;
                }
                // Case 2: ))
                else if (i - dp[i-1] > 0 && s.charAt(i - dp[i-1] - 1) == '(') {
                    dp[i] = dp[i-1] + 2;
                    if (i - dp[i-1] >= 2) {
                        dp[i] += dp[i - dp[i-1] - 2];
                    }
                }
                maxLength = Math.max(maxLength, dp[i]);
            }
        }
        
        return maxLength;
    }
}

C++ Solution


class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.length();
        if (n < 2) {
            return 0;
        }
        
        // Dynamic programming approach
        vector dp(n, 0);
        int maxLength = 0;
        
        for (int i = 1; i < n; i++) {
            if (s[i] == ')') {
                // Case 1: ()
                if (s[i-1] == '(') {
                    dp[i] = (i >= 2 ? dp[i-2] : 0) + 2;
                }
                // Case 2: ))
                else if (i - dp[i-1] > 0 && s[i - dp[i-1] - 1] == '(') {
                    dp[i] = dp[i-1] + 2;
                    if (i - dp[i-1] >= 2) {
                        dp[i] += dp[i - dp[i-1] - 2];
                    }
                }
                maxLength = max(maxLength, dp[i]);
            }
        }
        
        return maxLength;
    }
};

JavaScript Solution


/**
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses = function(s) {
    const n = s.length;
    if (n < 2) {
        return 0;
    }
    
    // Dynamic programming approach
    const dp = new Array(n).fill(0);
    let maxLength = 0;
    
    for (let i = 1; i < n; i++) {
        if (s[i] === ')') {
            // Case 1: ()
            if (s[i-1] === '(') {
                dp[i] = (i >= 2 ? dp[i-2] : 0) + 2;
            }
            // Case 2: ))
            else if (i - dp[i-1] > 0 && s[i - dp[i-1] - 1] === '(') {
                dp[i] = dp[i-1] + 2;
                if (i - dp[i-1] >= 2) {
                    dp[i] += dp[i - dp[i-1] - 2];
                }
            }
            maxLength = Math.max(maxLength, dp[i]);
        }
    }
    
    return maxLength;
};

C# Solution


public class Solution {
    public int LongestValidParentheses(string s) {
        int n = s.Length;
        if (n < 2) {
            return 0;
        }
        
        // Dynamic programming approach
        int[] dp = new int[n];
        int maxLength = 0;
        
        for (int i = 1; i < n; i++) {
            if (s[i] == ')') {
                // Case 1: ()
                if (s[i-1] == '(') {
                    dp[i] = (i >= 2 ? dp[i-2] : 0) + 2;
                }
                // Case 2: ))
                else if (i - dp[i-1] > 0 && s[i - dp[i-1] - 1] == '(') {
                    dp[i] = dp[i-1] + 2;
                    if (i - dp[i-1] >= 2) {
                        dp[i] += dp[i - dp[i-1] - 2];
                    }
                }
                maxLength = Math.Max(maxLength, dp[i]);
            }
        }
        
        return maxLength;
    }
}

Complexity Analysis

Time Complexity: O(n) where n is the length of the string
Space Complexity: O(n) to store the dynamic programming array

Solution Explanation

This solution uses dynamic programming to find the longest valid parentheses substring. Here's how it works:

Use a dp array where dp[i] represents the length of the longest valid substring ending at index i
For each closing parenthesis, consider two cases:
- Case 1: "()" pattern - add 2 to the previous valid length
- Case 2: "))" pattern - check if there's a matching '(' and combine lengths
Keep track of the maximum length found

Key points:

Only need to process closing parentheses
Handle both immediate pairs and nested pairs
Consider concatenation of valid substrings
Handle edge cases (empty string, single character)