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
Longest Valid Parentheses Constraints:
0 <= s.length <= 3 * 104
s[i]
is'('
, or')'
.
Longest Valid Parentheses Solutions
✅Time: O(n)
✅Space: O(n)
C++
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));
}
};
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();
}
}
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)
Watch Tutorial
Checkout more Solutions here