Longest Balanced Bracket Substring
Implement longestValidSubstring
Given a string
s consisting only of '(' and ')', find the length of the longest contiguous substring that is a balanced bracket sequenceBalancedEvery '(' in the substring has a matching ')' later within it, and every ')' has a matching '(' earlier within it — nothing left unmatched, anywhere in that stretch..
Checking every substring works but re-treads the same ground repeatedly. A single pass with a stack of indices (not characters) avoids that: keep a sentinel marking the last position that broke a run, push the index of every '(', and on every ')', pop the matching '(' off. Whatever's left on top afterward marks exactly where the current balanced run's boundary sits — so its length is simply the current index minus that value, read off directly with no re-scanning. If a ')' ever finds nothing to pop (the stack was already down to just the sentinel), it becomes the new sentinel itself, since no balanced run can reach back across an unmatched closing bracket.
Example 1:
Input: s = "()(())"
Output: 6
Example 2:
Input: s = ")((())"
Output: 4
Example 3:
Input: s = "(()()"
Output: 4
+ 7 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ s.length ≤ 20 - ●
s consists only of the characters '(' and ')'
s =
()(())