Loading...
Loading...
Loading...
Rohan's code editor lost some of his brackets. It now shows only a line of ( and ).
A piece of the line is valid when every ( in it has a matching ) after it, and every ) matches an earlier ( inside the same piece. For example (())() is valid, but ())( is not.
Print the length of the longest valid continuous piece of the line. Print 0 if there is none.
( and ), with no spaces.Example 1
Input
)()())
Output
4
The middle piece ()() is valid, so the answer is 4.
Example 2
Input
()(()
Output
2
There are two matched pairs, but the unmatched ( between them splits the line. The longest valid piece is 2.
Try the problem first. Open one hint at a time.
Matching a ) always means finding the most recent ( that is still open.
When a ) matches, the valid piece ending here starts just after the last position that could not be part of any valid piece.
Keep positions, not characters. Start with a marker -1 at the bottom. A ) that has nothing to match becomes the new marker.
Use a stack of indexes: push the index of each (. On ), pop; if the stack is now empty push this index, otherwise the length is i − top.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor