Longest Well-Formed Bracket Run
You get a string s. Every character in it is ( or ).
A string of brackets is well-formed when:
- it has the same number of
(and), and - reading it from left to right, the count of
)is never larger than the count of(read so far.
Find the longest substring of s (a part of s with no gaps) that is well-formed. Return its length. If there is no such substring, return 0. An empty string s also gives 0.
Hint
Keep a stack of indices. Start with -1 on the stack, as the position just before the current run. Push the index of each (. For each ), pop one index. If the stack is now empty, push the current index as the new "before the run" position. Otherwise, the current run length is the current index minus the index on top of the stack. This is O(n).
Examples
Example 1
- Input:
- ")(()())("
- Output:
- 6
The substring "(()())" from index 1 to index 6 is well-formed and has length 6.
Example 2
- Input:
- "()(()"
- Output:
- 2
The "(" at index 2 is never closed, so it breaks the string. The best runs are "()" at the start and "()" at the end, each of length 2.
Example 3
- Input:
- "))(("
- Output:
- 0
No substring is well-formed, so the answer is 0.
Constraints
0 <= s.length <= 60- Every character of
sis(or).
Run checks your code against the 3 examples. Submit checks it against all 203 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.