Longest Balanced Bracket Stretch

Hard

You are given a string brackets made only of the characters ( and ). A bracket sequence is *balanced* when every opening bracket has a matching closing bracket to its right and the pairs never cross: (())() is balanced, while )( and (() are not. Return the length of the longest balanced stretch (a run of consecutive characters) of brackets. If there is no non-empty balanced stretch, return 0.

Example 1

brackets=")(()())(" → 6

The piece (()()) from position 1 to 6 is balanced and has length 6. The outer brackets cannot be added to it.

Example 2

brackets="()(()" → 2

Both the leading () and the trailing () are balanced, but the extra ( between them keeps them apart, so the answer is 2.

Example 3

brackets=")))" → 0

There are only closing brackets, so no non-empty balanced piece exists.

Constraints

0 ≤ len(brackets) ≤ 3 · 10⁴
every character of brackets is ( or )

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Stack String Dynamic Programming

Similar problems

Clear the Marble Row Hard Flip the Circuit Output Hard Grading the Arithmetic Quiz Hard Brackets With Wildcards Medium a's Then b's With the Fewest Deletions Medium

Input

brackets=")(()())("

Expected

Run checks the first 3 tests in your browser. Submit checks all 136 tests on the server, hidden ones included.