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

and `')'`

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

**Example 1:**

Input:s = "(()"Output:2Explanation:The longest valid parentheses substring is "()".

**Example 2:**

Input:s = ")()())"Output:4Explanation:The longest valid parentheses substring is "()()".

**Example 3:**

Input:s = ""Output:0

**Constraints:**

`0 <= s.length <= 3 * 10`

^{4}`s[i]`

is`'('`

, or`')'`

.

class Solution {
public int longestValidParentheses(String s) {
if(s==null){
return 0;
}
int len = s.length();
int[] dp = new int[len];
int open = 0;
int ans = 0;
for(int i=0;i<len;i++){
char ch = s.charAt(i);
if(ch=='('){
open++;
}
else if(open >0){
dp[i] = 2 + dp[i-1];
if(i-dp[i] > 0){
dp[i] = dp[i] + dp[i-dp[i]];
}
open--;
}
ans = Math.max(ans, dp[i]);
}
return ans;
}
}

This question can be solved using both the Stack-based approach and the Dynamic programming approach. Both of the approaches are discussed in detail in the video.

Time Complexity: O(n)

Space Complexity: O(n)