# GeetCode Hub

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

Constraints:

• `0 <= s.length <= 3 * 104`
• `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)