#191HardStacks· Index Stack for Brackets

Longest Well-Formed Run

A code formatter scans a line made only of the characters `(` and `)`. It wants to find the longest **contiguous** stretch of the line that is well formed: every opening bracket in the stretch is matched by a closing bracket later in the same stretch, every closing bracket is matched by an opening bracket earlier in it, and the matching pairs nest properly. The empty stretch is well formed. Given the string `s`, return the length of the longest well-formed contiguous substring.

Input format

`s`: a string consisting only of the characters ( and ).

Output format

An integer: the length of the longest well-formed substring (0 if there is none).

Examples

Input: s = "(()"

Output: 2

The longest well-formed substring is "()" at the end, of length 2.

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

Output: 4

The substring "()()" in the middle is well formed and has length 4.

Input: s = ""

Output: 0

An empty line has no brackets.

Constraints

0 <= s.length <= 10^5
s contains only ( and ) characters.

#stack
#dynamic-programming
#strings
#parentheses