ParenthesisRemoval | Topcoder Archive

Problem Statement

Correct parentheses 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 parentheses sequence can be derived using the above rules.

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

You are given a String s that is guaranteed to be a correct parentheses sequence. A removal is an action that consists of two steps:

Remove the first opening parenthesis in s.
Remove one closing parenthesis in s. After you do so, s must again be a correct parentheses sequence.

Compute and return the number of distinct ways in which s can be reduced to an empty string by performing consecutive removals, modulo 10^9+7. Two ways are considered distinct if there is a step in which you remove a different closing parenthesis. (See Example 1 for clarification.)

Definition

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

Constraints

s will have between 2 and 2,500 characters, inclusive.
s will be a correct parentheses sequence.

Examples

```
"()()()()()"
```
```
Returns: 1
```
In each removal we have to choose the leftmost closing parenthesis.
```
"(((())))"
```
```
Returns: 24
```
In each removal we can choose any closing parenthesis we want. Note that these count as distint choices, even though all choices lead to the same string. Thus, there are 4*3*2*1 = 24 different sequences of removals that change s into an empty string.
```
"((()()()))"
```
```
Returns: 54
```
Below is one of the 54 possible sequences of removals. Remember that in each step we also remove the first opening parenthesis. Remove the fourth closing parenthesis: "(()()())" Remove the second closing parenthesis: "()(())" Remove the first closing parenthesis: "(())" Remove the second closing parenthesis: "()" Remove the first closing parenthesis: ""
```
"(())(())(())"
```
```
Returns: 8
```

"((((())((((((((((()((((((()))))())))))()))))))))))"

Returns: 948334170

Don't forget about the mod.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.