In this post, we are going to solve the Longest Valid Parentheses Leetcode Solution problem of Leetcode. This Leetcode problem is done in many programming languages like C++, Java, and Python.

Problem
Given a string containing just the characters '('
and ')'
, find 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:
Now, let’s see the leetcode solution of Longest Valid Parentheses Leetcode Solution.
Longest Valid Parentheses Leetcode Solution in Python
class Solution: def longestValidParentheses(self, s: str) -> int: s2 = ')' + s # dp[i] := Length of longest valid parentheses substring of 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)
Longest Valid Parentheses Leetcode Solution in CPP
class Solution { public: int longestValidParentheses(string s) { const string s2 = ")" + s; // dp[i] := Length of longest valid parentheses substring of 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 *max_element(begin(dp), end(dp)); } };
Longest Valid Parentheses Leetcode Solution in Java
class Solution { public int longestValidParentheses(String s) { final String s2 = ")" + s; // dp[i] := Length of longest valid parentheses substring of 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(); } }
Note: This problem Longest Valid Parentheses is generated by Leetcode but the solution is provided by Chase2learn This tutorial is only for Educational and Learning purposes.