• 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)
``````