All Tracks Data Structures Arrays 1-D Problem

Bracket sequences
Tag(s):

1-D array, Arrays, Data Structures

Problem
Editorial
Analytics

A bracket sequence is a string that contains only characters '(' and ')'.

A correct bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters '1' and '+' between the original characters of the sequence. For example, bracket sequences '()()' and '(())' are correct. The resulting expressions of these sequences are: '(1)+(1)' and '((1+1)+1)'. However, '(', ')(', and '(' are incorrect bracket sequences. 

You are given a bracket sequence \(s(s_1 s_2 ... s_n)\), where \(s_i\) denotes the type of \(i\)'s bracket (open or close). It is not mandatory that \(s\) is necessarily correct. Your task is to determine the number of \(i\)'s such that \(s_i s_{i+1} ... s_n s_1 s_2 ... s_{i-1}\) is a correct bracket sequence.

Input format

The single line contains sequence \(s\).

Output format 

Print the number of shifts denoting the correct bracket sequence.

Constraints

\(|s| \le 5\times 10^5\)

SAMPLE INPUT
)()()(
SAMPLE OUTPUT
3
Explanation

For all \(i=2,4,6 \), shift of string will be ()()(), which is correct bracket sequence. Since, answer is 3

Time Limit: 3.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, C++17, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, Java 14, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, Python 3.8, R(RScript), Racket, Ruby, Rust, Scala, Swift-4.1, Swift, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

May Easy '20

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?