TopCoder Statistics - Problem Statement

Problem Statement

Correct bracket sequences can be defined recursively as follows:

The empty string "" is a correct sequence.
If "X" and "Y" are correct sequences, then "XY" (the concatenation of X and Y) is a correct sequence.
If "X" is a correct sequence, then "(X)" is a correct sequence.
Each correct bracket sequence can be derived using the above rules.

Examples of correct bracket sequences include "", "()", "()()()", "(()())", and "(((())))".

A string T is called a subsequence of a string S if we can erase some (possibly none or all) characters of S to obtain T. For example, "bdf" is a subsequence of "abcdefg".

You are given a String s that consists of the characters '(' and ')' only. Let X be the number of different non-empty subsequences of s that are correct bracket sequences. Note that each distinct subsequence should only be counted once, even if it can be obtained from s in multiple ways. (See the examples for clarification.) Compute and return the value (X modulo 1,000,000,007).

Definition

Class:: BracketSequenceDiv2
Method:: count
Parameters:: String
Returns:: int
Method signature:: int count(String s)
(be sure your method is public)

Constraints

s will contain between 1 and 100 characters, inclusive.
Each character in s will be '(' or ')'.

Examples

"(())("

Returns: 2

Correct non-empty bracket subsequences are "()" and "(())".
"())"

Returns: 1

Only "()" is suitable.
")((("

Returns: 0

There are no non-empty correct bracket subsequences.
"()()()()()()()()(())))(()()()()))())"

Returns: 364675
"()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()"

Returns: 122826009

Do not forget to take answer modulo 1,000,000,007.
"(((((((((((((((((((((((((((((((((((((((((((((((((())))))))))))))))))))))))))))))))))))))))))))))))))"

Returns: 50
"()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()"

Returns: 122826009
"))))))))))))(((((((((((("

Returns: 0
"())(())()(()())()()(()()())()(()()())(())(()())()(()()()()()())()()()()(())()()(())(())()()()()(()()"

Returns: 331970039
"())()(())()()(())()()(()()())(())(())(())()(())(()())()()(()()())(()())()()()()(()()())(()())(())(()"

Returns: 604185089
"()))()))(()(()((())()))()(())(()()))))(()()()"

Returns: 1148466
")()(()))(((((()(()()(()))())))((())(())))))())(()()))()"

Returns: 36915289
"()())()())())())))()))(((())()()())(())())(()"

Returns: 1225415
"()))(()((()(()))()(())(()))(()))()(((((((()(("

Returns: 93751
")((())()())(()()()())()()()()((())())))()((()"

Returns: 3206464
"(()()()(((()(((())()(((()((())((())((())))(((((()((())))()()))()()()())(()((())))()()((()(((()(()())"

Returns: 452026838
"())()(())))((((()))(()()((()((())())((())(()))(())()()()(((((()()))((()()(((((())))())(((((())))))(("

Returns: 21720547
"((()()())))))((()(()))(((()(()()))))))((((()(((()((()()()))(())))())()))((()))())(((()())()()))()((("

Returns: 618775716
"(())))((()()))()())(()(()(((())))()(())))))()((()))(()))()))(()(()()()(()))))))))())())(((()))()(()("

Returns: 185911238
")())(()(())(())(()(()()((()()(((()((())((((()(()()())())))(((())((((()(()(())(()())))(((((()))(())()"

Returns: 368876257
"((())))))(())))("

Returns: 16
")(()()("

Returns: 3

Statistics

Problem Statement for "BracketSequenceDiv2"

Problem Statement

Definition

Constraints

Examples