How do you solve Longest Valid Parentheses on LeetCode?

Longest Valid Parentheses (LeetCode #32) can be solved using Brute Force or Optimal Solution (Dynamic Programming). The optimal approach is Optimal Solution (Dynamic Programming) with O(n) time complexity and O(n) space complexity. Key insight: Recognizing that valid parentheses must be balanced and can be checked incrementally helps in optimizing the solution.

What is the brute force solution for Longest Valid Parentheses?

The brute force approach for Longest Valid Parentheses is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves generating all possible substrings of the input string and checking if they are valid parentheses. This method is straightforward but inefficient, as it checks every combination. The optimal Optimal Solution (Dynamic Programming) approach improves this to O(n).

What algorithm or data structure is used to solve Longest Valid Parentheses?

Longest Valid Parentheses uses the following concepts: String, Dynamic Programming, Stack. The recommended patterns to study are: Hash Map, Array, Two Pointers.

What are the interview tips for Longest Valid Parentheses?

When you first see this problem, mention that you will explore both brute force and optimal solutions to demonstrate your understanding. Communicate your approach clearly, explaining how you will check for valid parentheses and how you will keep track of lengths. Be sure to mention edge cases, such as strings that are entirely invalid or empty, to show that you are thinking critically about the problem.

What are common mistakes when solving Longest Valid Parentheses?

Students often forget to check for edge cases, such as empty strings or strings with no valid parentheses. Another common mistake is not correctly updating the DP array based on previous valid lengths.

#32

Longest Valid Parentheses

Hard

StringDynamic ProgrammingStackHash MapArrayTwo Pointers

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution (Dynamic Programming)★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal approach uses dynamic programming to keep track of the lengths of valid parentheses substrings. This method is efficient because it builds on previously computed results, avoiding the need to check every substring.

⚙️

Algorithm

4 steps

1Step 1: Initialize a DP array of the same length as the input string, filled with zeros.
2Step 2: Iterate through the string starting from index 1. For each closing parenthesis, check if it forms a valid pair with an opening parenthesis.
3Step 3: If it does, update the DP array based on previous valid lengths to calculate the current valid length.
4Step 4: Keep track of the maximum length found during the iteration.

solution.py16 lines

1# Full working Python code with comments
2
3def longest_valid_parentheses(s):
4    max_length = 0
5    dp = [0] * len(s)
6    for i in range(1, len(s)):
7        if s[i] == ')':
8            if s[i - 1] == '(':  # Case: '()'
9                dp[i] = (dp[i - 2] if i >= 2 else 0) + 2
10            elif i - dp[i - 1] > 0 and s[i - dp[i - 1] - 1] == '(':  # Case: '...()'
11                dp[i] = dp[i - 1] + (dp[i - dp[i - 1] - 2] if i - dp[i - 1] >= 2 else 0) + 2
12            max_length = max(max_length, dp[i])
13    return max_length
14
15# Example usage
16print(longest_valid_parentheses('(()'))  # Output: 2

ℹ

Complexity note: The time complexity is O(n) because we only traverse the string once, and the space complexity is O(n) due to the DP array storing lengths of valid parentheses.

1Recognizing that valid parentheses must be balanced and can be checked incrementally helps in optimizing the solution.
2Using dynamic programming allows us to build on previously computed results, which is a common pattern in many string-related problems.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.