Longest Valid Parentheses

Given a string containing just the characters '(' and ')', return the length of the longest valid (well-formed) parentheses substring.

Examples

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 * 10^4
• s[i] is '(' or ')'

Function Signature

function longestValidParentheses(s) {
  // Your code here
}

Test Cases

• Base cases: s = "" → 0, s = "(" → 0, s = ")" → 0
• Simple cases: s = "()" → 2, s = "(()" → 2, s = "())" → 2
• Medium cases: s = ")()())" → 4, s = "((()))" → 6
• Edge cases: s = "()()()" → 6, s = "(((((" → 0
• Complex cases: s = "(()())" → 6, s = "()(()" → 2

Notes

• Valid parentheses must be properly nested and balanced
• A substring is a contiguous sequence of characters
• Need to find the longest such substring
• Empty string returns 0
• Single characters are never valid
• Optimal solution uses stack with O(n) time complexity