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.
