Find the longest valid bracket sequence
The C++ programming language uses curly braces
{ and } to separate scopes. You’re trying to parse a C++ code and would like to make sure it’s syntactically correct. The first step is to make sure the opening curly braces match the closing ones.You’ve decided to write a program that given a list of curly braces would print the longest sequence of curly braces starting from the very beginning that’s valid.
Input
The only line of the input contains a string
b (1 ≤ |b| ≤ ) containing curly braces.Output
The program should print the length of the longest sequence of curly braces that’s valid and starts from the beginning.
Examples
Input | Output |
{{}} | 4 |
{{{} | 0 |
}{{} | 0 |
{}{{{{} | 2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB