BracketSequenceDiv1 | Topcoder Archive

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)" and "[X]" are also correct sequences.
Each correct bracket sequence can be derived using the above rules.

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

You are given a String s that only contains the characters '(', ')', '[', and ']'. We want to erase some subset of characters of s (possibly none of them, but not all of them). Moreover, we want to do it in such a way that the resulting string will be a correct non-empty bracket sequence. Compute and return the number of ways in which this can be done.

Definition

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

Constraints

s will contain between 1 and 40 characters, inclusive.
Each character in s will be one of '(', ')', '[', ']'.

Examples

```
"()[]"
```
```
Returns: 3
```
There are 3 valid ways to erase some characters and obtain a correct non-empty bracket sequence: Erase nothing and obtain "()[]". Erase the first two characters and obtain "[]". Erase the last two characters and obtain "()".
```
"())"
```
```
Returns: 2
```
Here we have 2 solutions: we can either erase the middle character or the last character. Note that we count each of those ways separately, even though in both cases we get the same string "()".
```
"()()"
```
```
Returns: 4
```
```
"([)]"
```
```
Returns: 2
```
```
"())[]][]([]()]]()]]]"
```
```
Returns: 3854
```

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.