# 32. Longest Valid Parentheses

• Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution { public: int longestValidParentheses(string s) { const string s2 = ")" + s; // dp[i] := Length of longest valid parentheses substring of s2[1..i] vector 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(dp.begin(), dp.end()); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 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(); } } 
  1 2 3 4 5 6 7 8 9 10 11 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)