A code editor highlights the longest contiguous stretch of a line that is a well-formed sequence of round brackets. Given a string of ( and ), print the length of the longest well-formed substring.
Constraints
- 1 ≤ length ≤ 100000
Input and output
- Input
- One line: a string of ( and ).
- Output
- One integer.
Examples
Input 1
)()())Output
4The middle "()()" is the longest well-formed stretch: 4.
Input 2
(((Output
0Nothing ever closes, so 0.
Show hints
- Push indices, not characters.
- Keep the index of the last unmatched ")" (or −1) at the bottom of the stack as a boundary.
Show the explanation
Keep a stack of indices, starting with −1 as a boundary. For (, push its index. For ), pop; if the stack becomes empty, this ) is unmatched, so push its index as the new boundary; otherwise the current valid stretch runs from the index now on top + 1 to here, so its length is i − top. Track the maximum. One pass, O(n).
Original UniCircle question. Last reviewed 22 Oct 2026.