Longest Valid Parentheses

Hard

Strings Dynamic Programming Stack Dynamic Programming Monotonic Stack

Problem

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

A valid parentheses substring is one where every opening parenthesis '(' has a corresponding closing parenthesis ')' and they are properly nested.

Constraints

0 <= s.length <= 3 * 10^4
s[i] is '(' or ')'

Examples

Input: s = "(()"

Output: 2

The longest valid parentheses substring is "()".

Input: s = ")()())"

Output: 4

The longest valid parentheses substring is "()()".

Input: s = ""

Output: 0

An empty string has no valid parentheses.

Loading...

Loading Python...