BracketSequenceDiv1

SRM 686 · 2016-03-02 · by Arterm

SRM 686 · 2016-03-02 · by Arterm · Dynamic Programming

Show categories

Class Name: BracketSequenceDiv1

Return Type: long

Method Name: count

Arg Types: (string)

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.

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

Submissions are judged against all 26 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class BracketSequenceDiv1 with a public method long long count(string s) · 26 test cases · 2 s / 256 MB per case