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)