Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Is This a Give-Away?

By msi1427 · Limits 2s, 512 MB

Once there lived an ancient mage named Farabi. He could always give perfect weather forecast. He never revealed how. After he died no one could predict the weather perfectly anymore. In his lifetime, he wrote a book in an encrypted language. After so many years and so many trials, a brilliant coder named Masum broke the encryption.

After decryption, Masum found out the key to the weather forecast. Considering the waves of the rivers around, he can get a sequence consisting of curly braces (‘{’, ‘}’). The maximum depth that can be achieved after removing some or no curly braces, that means the depth of maximum nested curly bracket sequence that can be created, is the key to everything. Masum wants you to build a system for it while he finds out the sequence.

For example, in the bracket sequence “{{}}{}” The maximum depth is 2.

Input

Input contains a string s containing ‘{’ and ‘}’ only.

|s|<=105

Output

Print one integer denoting the answer.

Sample

InputOutput
{{}{}{}}
3

Explanation:

In the given sample, if we remove the 3rd and 6th braces, we will get {{{}}} which will have a depth 3. There is no other way to get more than 3.

Discussion

Statistics


79% Solution Ratio

Mr_BangladeshEarliest, 7M ago

Circle.21Fastest, 0.0s

Circle.21Lightest, 131 kB

mdvirusShortest, 273B

Submit

Login to submit

Related Contests