**Difficulty: Hard**

**Frequency: N/A**

Given a string containing just the characters `'('`

and `')'`

, find the length of the longest valid (well-formed) parentheses substring.

For `"(()"`

, the longest valid parentheses substring is `"()"`

, which has length = 2.

Another example is `")()())"`

, where the longest valid parentheses substring is `"()()"`

, which has length = 4.

**Test Cases:**

**Solution 1:**

**Data structure:**

**Steps:**

**Complexity:**

**Code:**

class Solution { public: int longestValidParentheses(string s) { int n = s.size(); if (n <= 1) return 0; vector<int> dp(s.size(), 0); int maxL = 0; for (int i = 1; i < n; i++) { if (s[i] == ')') { if (s[i - 1] == '(') { dp[i] = i - 2 >= 0 ? dp[i - 2] + 2 : 2; maxL = max(maxL, dp[i]); } else { if (i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] == '(') { dp[i] = dp[i - 1] + 2 + (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0); maxL = max(maxL, dp[i]); } } } } return maxL; } };

**Solution 2:**

**Data structure:**

**steps:**

**Complexity**:

**Code**:

**Submission errors:**

**Things to learn:**