Practice/Meta/Leetcode 32. Longest Valid Parentheses

Leetcode 32. Longest Valid Parentheses

CodingMust

Problem

Given a string containing only the characters '(' and ')', determine the length of the longest contiguous substring that forms a valid (properly matched and balanced) sequence of parentheses.

A valid parentheses string means:

• Every opening parenthesis has a corresponding closing parenthesis
• The parentheses are properly nested (no closing before its matching opening)

You need to find the maximum length among all possible valid substrings within the input string.

Requirements

1. Return the length as an integer (not the substring itself)
2. Handle strings with invalid parentheses that cannot be matched
3. Consider both nested patterns like "(())" and adjacent patterns like "()()"
4. The valid substring must be contiguous in the original string

Constraints

• 0 ≤ length of string ≤ 30,000
• String contains only '(' and ')' characters
• Target time complexity: O(n) where n is the length of the string
• Target space complexity: O(n) or better

Examples

Example 1:

Input: s = "(()" Output: 2 Explanation: The longest valid parentheses substring is "()" at the end, which has length 2.

Example 2:

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

Example 3:

Input: s = "(()())" Output: 6 Explanation: The entire string is a valid parentheses sequence with length 6.

Example 4:

Input: s = "" Output: 0 Explanation: An empty string has no parentheses, so the answer is 0.