417. Longest Valid Brackets
A text editor highlights well-formed bracket runs. The text s contains only the characters '(' and ')'. A substring (a contiguous piece of the text) is well-formed when every opening bracket in it is closed by a later closing bracket, brackets are matched like in arithmetic, and no closing bracket appears without a partner inside the piece.
Return the length of the longest well-formed substring of s. If there is none, return 0. The matching bracket pairs must lie entirely inside the chosen piece, so for example "(()" contains the well-formed piece "()" of length 2 but not itself. The text may have up to 100,000 characters, which rules out testing every substring.
Example 1
- Input:
- s = "))(()())(()"
- Output:
- 6
- Explanation:
The middle piece
(()())is well-formed and has length 6, while the tail(()only yields a piece of length 2.
Example 2
- Input:
- s = "(()))()()()(("
- Output:
- 6
- Explanation:
The piece
()()()in the middle is well-formed with length 6, while the first piece(())only has length 4, so the answer is 6.
Constraints
0 ≤ s.length ≤ 105
s[i] is either '(' or ')'.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 400 msC++ 100 msJava 200 msJavaScript 200 msTypeScript 200 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)