32. Longest Valid Parentheses LeetCode Solution

In this guide we will provide 32. Longest Valid Parentheses LeetCode Solution with best time and space complexity. The solution to Longest Valid Parentheses problem is provided in various programming languages like C++, Java and python. This will be helpful for you if you are preparing for placements, hackathon, interviews or practice purposes. The solutions provided here are very easy to follow and with detailed explanations.

Problem Statement

Complexity Analysis

Longest Valid Parentheses solution in C++
Longest Valid Parentheses soution in Java
Longest Valid Parentheses solution Python
Additional Resources

32. Longest Valid Parentheses LeetCode Solution image

Problem Statement of Longest Valid Parentheses

Given a string containing just the characters ‘(‘ and ‘)’, return the length of the longest valid (well-formed) parentheses substring.

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

Constraints:

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

Complexity Analysis

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

32. Longest Valid Parentheses LeetCode Solution in C++

class Solution {
 public:
  int longestValidParentheses(string s) {
    const string s2 = ")" + s;
    // dp[i] := the length of the longest valid parentheses in the substring
    // s2[1..i]
    vector<int> dp(s2.length());

    for (int i = 1; i < s2.length(); ++i)
      if (s2[i] == ')' && s2[i - dp[i - 1] - 1] == '(')
        dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2;

    return ranges::max(dp);
  }
};
/* code provided by PROGIEZ */

32. Longest Valid Parentheses LeetCode Solution in Java

class Solution {
  public int longestValidParentheses(String s) {
    final String s2 = ")" + s;
    // dp[i] := the length of the longest valid parentheses in the substring
    // s2[1..i]
    int dp[] = new int[s2.length()];

    for (int i = 1; i < s2.length(); ++i)
      if (s2.charAt(i) == ')' && s2.charAt(i - dp[i - 1] - 1) == '(')
        dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2;

    return Arrays.stream(dp).max().getAsInt();
  }
}
// code provided by PROGIEZ

32. Longest Valid Parentheses LeetCode Solution in Python

class Solution:
  def longestValidParentheses(self, s: str) -> int:
    s2 = ')' + s
    # dp[i] := the length of the longest valid parentheses in the substring
    # s2[1..i]
    dp = [0] * len(s2)

    for i in range(1, len(s2)):
      if s2[i] == ')' and s2[i - dp[i - 1] - 1] == '(':
        dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2

    return max(dp)
 #code by PROGIEZ