Statistics

Problem Statement for "BracketSequenceDiv1"

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

  1. "()[]"

    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 "()".

  2. "())"

    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 "()".

  3. "()()"

    Returns: 4

  4. "([)]"

    Returns: 2

  5. "())[]][]([]()]]()]]]"

    Returns: 3854

  6. "(((((((((((((((((((())))))))))))))))))))"

    Returns: 137846528819

  7. "[][][][][][][][][][][][][][][][][][][][]"

    Returns: 24466267019

  8. "))))))))))))((((((((((((]]]]]]]]]]][[[["

    Returns: 0

  9. "()[]()[][]()()[][][]()()()[][]()()()[]()"

    Returns: 1058874671

  10. "[]()()[][]()()()()()()[][][][][]()[][][]"

    Returns: 1682926959

  11. "[(]]]][()(][)[[](]][()([("

    Returns: 3057

  12. ")]([])]))]]](()"

    Returns: 47

  13. ")([[[]]((([((]("

    Returns: 29

  14. "(]([[]([][()]()"

    Returns: 355

  15. ")((][)[][)[()]]"

    Returns: 184

  16. "()]([]][]()[)[([)[([))[[](())()[)([([))]"

    Returns: 22416206

  17. "]]([][]))(][(([][][[)][))](]][)][([([[(]"

    Returns: 1256040

  18. "(][(][)][][)][[()((]])](])[[)(][([])([[)"

    Returns: 5724814

  19. "][]((]))([))[]])[((][)(]]]((]][)]))))())"

    Returns: 16479684

  20. "(]((][(()][)[([[)([)])])]])](]([)]()(][("

    Returns: 4178817

  21. "([([([([([([([([([([([([([([([([([([([(["

    Returns: 0

  22. "()()()()()()()()()()()()()()()()()()()()"

    Returns: 24466267019

  23. "[([([([([([([([([([([([([([([([([([([([("

    Returns: 0

  24. "([([([(((([([([([[[[]]]]]])]]])))]))))))"

    Returns: 873535479

  25. "([([([([([([([([([([])])])])])])])])])])"

    Returns: 506376221

  26. "(((((((((((((((((((((((((((((((((((((((("

    Returns: 0

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.
This problem was used for: