Statistics

Problem Statement for "Bracket107"

Problem Statement

Correct bracket sequences are strings in which each character is a '(' or a ')', the total number of opening brackets is the same as the total number of closing brackets, and each prefix contains at least as many opening as closing brackets. For example, the shortest few correct bracket sequences are "", "()", "(())", and "()()".

The subsequence of a string S is any string that can be obtained by erasing zero or more characters of S. For example, each of the strings "", "ace", and "abcde" is a subsequence of "abcde".

We will use LCS(S,T) to denote the length of a longest common subsequence of strings S and T. In other words, LCS(S,T) is the largest k such that there is a string U of length k that is both a subsequence of S and a subsequence of T. For example, LCS("abcde","bad") = 2.

You are given a String s that contains a correct bracket sequence.

You are looking for a string t with the following properties:
  • t will have the same length as s,
  • t will be a correct bracket sequence,
  • t will not be equal to s,
  • LCS(s,t) will be as large as possible.
Compute and return the number of strings with these properties.

Definition

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

Notes

  • You may assume that the answer for each valid test case fits into a signed 32-bit integer variable.

Constraints

  • s will contain between 4 and 50 characters, inclusive.
  • Each character in s will be either '(' or ')'.
  • s will be a correct bracket sequence.

Examples

  1. "(())"

    Returns: 1

    There is only one other correct bracket sequence of the same length.

  2. "(())()"

    Returns: 3

    There are four other correct bracket sequences of the same length: "((()))", "()(())", "()()()", and "(()())". However, only in three of those four cases the length of the longest common subsequence is 5. LCS( "(())()", "()(())" ) is only 4, therefore "()(())" is not a valid choice of the string t.

  3. "()()()"

    Returns: 3

  4. "(((())))"

    Returns: 5

  5. "((())())"

    Returns: 9

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

    Returns: 237

  7. "()()()(())()()(((())))(())()()()()()()(())()(())()"

    Returns: 389

  8. "()()()()()(())()()((()))()()()()()"

    Returns: 189

  9. "(((((((((()(((((((()(()(((()))))))))))))))))))))"

    Returns: 177

  10. "(()())(((((((((((((((()((()()(()))))))))))))))))))"

    Returns: 218

  11. "(((((((()(((((((()((()((()(()())))))))))))))))))))"

    Returns: 276

  12. "((()((()))))"

    Returns: 17

  13. "()()()((((((((())()())((()()())))()(()()())))))())"

    Returns: 529

  14. "()()()()()()()()(())((()))()()()"

    Returns: 153

  15. "(((((())((()()))((((((()()((())))(((()))))))))))))"

    Returns: 320

  16. "(())(())(()((((()(((()))))))))"

    Returns: 93

  17. "()()()()()()()(()())()()(((()))())()((())()())()"

    Returns: 386

  18. "(()((((((((()((((((()((((()())))))))))))))))))))"

    Returns: 220

  19. "()(((())))()()()()(())()()()()()(()()())(()(()))()"

    Returns: 398

  20. "()()()()()()()()(())()()()()()()()()()()()()()()"

    Returns: 388

  21. "(())()()(())()()()()(()()())()(())(())()()()(())"

    Returns: 379

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

    Returns: 133

  23. "(()())(()())()()()()((()))(()())(())(()(()()))()()"

    Returns: 393

  24. "()()"

    Returns: 1

  25. "()((()((()()())))(((())(((())()(())(()))()()))))"

    Returns: 489

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

    Returns: 373

  27. "((()()()(())(())((((())(())))))(((((()()))))))"

    Returns: 372

  28. "()()(())()()()()()()()()()()()()()(())()"

    Returns: 233

  29. "(())()()()()()()()()()()(((()()())))()((()(())))"

    Returns: 333

  30. "(()((()()())()((()))())()(((()()))))"

    Returns: 314

  31. "()()()(((((()()((()((()())(()()))()((())))))))))"

    Returns: 428

  32. "(()(()((((((((((()))))))))))))"

    Returns: 79

  33. "()()(())()()()()()()()()()()()(())((()))()()()()()"

    Returns: 408

  34. "(((((((((((((((((())))))))))))))))))"

    Returns: 33

  35. "()(())()(()())()()((()()))()()()()(())((()))()"

    Returns: 328

  36. "()((((()))(()(()())())))"

    Returns: 105

  37. "((()(()))()())(())((()(()())))(())()(())(()())()()"

    Returns: 374

  38. "()(((()()())()))()(()())(()(()()))(())"

    Returns: 229

  39. "()()((((((())))))()()((()()))()()(((()())())))"

    Returns: 432

  40. "()()()(((((()(((()(()())(())))))))))"

    Returns: 190

  41. "(((((((((((((((((((()(((()))))))))))))))))))))))"

    Returns: 89

  42. "(((()()((((((((((((((()())))))))))))))))))"

    Returns: 150

  43. "()()()()()()()()()()()()()(())()()()()()()()()()"

    Returns: 393

  44. "()()()()()()()()()()()(()())()()"

    Returns: 156

  45. "()()(()())(())((()(((()((()(((((()))))))))))))"

    Returns: 246

  46. "(())()()()()()()()()()()()()()()()()"

    Returns: 153

  47. "(((((((((())())((()(((((((((()))))))))))))))))))"

    Returns: 177

  48. "((()(((()()))(()(()(())(()()))))))"

    Returns: 239

  49. "(()(()((((((()))(((()(((((()((()))))))))))))))))"

    Returns: 265

  50. "((((()))))()(()())(((()))())()(((()))(()))"

    Returns: 188

  51. "(())((((()))(()((((())()((()())(())())))()))))"

    Returns: 380

  52. "(()(()(()())())()()(((())()(()(((())()()))()))))"

    Returns: 609

  53. "(())(()())()(()(())((())()))()()()()(()())()()()"

    Returns: 387

  54. "()()()()()()(()()()())()(())()()()()(())()()(())()"

    Returns: 458

  55. "((((((((((((((((((((((((()))))))))))))))))))))))))"

    Returns: 47

  56. "()()()()()()()()()()()()()()()()"

    Returns: 120

  57. "((((((((((((((((()(((((())))))))))))))))))))))"

    Returns: 85

  58. "((((()()((((((((((((()))))))))))))))))"

    Returns: 101

  59. "()(()(())()()()()())()(())()()(())()((()))()(()())"

    Returns: 440

  60. "()(((())(((((()))))(((()((()()()))))))))"

    Returns: 225

  61. "()(())(())((()))((())()())(())(()()()())(()())"

    Returns: 307

  62. "()()(()()())()(((())(()())))()()"

    Returns: 168

  63. "((()()(()()((()(((())((()((((((())))))))))))))))"

    Returns: 349

  64. "()(())()()()()((()()(())(()))()())()()"

    Returns: 272

  65. "((()(((()(((()()(())(()((((((())))))))))))))))"

    Returns: 293

  66. "()(()()(()()()()))"

    Returns: 75

  67. "((((((((((((((((((((((((()))))))))))))))))))))))))"

    Returns: 47

  68. "(((()(())(())()()(((()(()(()))))))))"

    Returns: 253

  69. "((()))((())()(()))(()(()))(())(((())()()))(()())"

    Returns: 292

  70. "()(()()()((()((((()((()))((())))))))))"

    Returns: 243

  71. "(()((()())())()((((()()((()()((()())()))))))))"

    Returns: 498

  72. "()()()()()()(())(())()()()()()"

    Returns: 145

  73. "()()()()()()()()()()()()()()()()()()()()()()()"

    Returns: 253

  74. "((((((((((((((()))))))))))))))"

    Returns: 27

  75. "((((()((((((()(()(((()((((()(())))))))))))))))))))"

    Returns: 277

  76. "()()(((())))()(((()))(()))()(())(())()"

    Returns: 178

  77. "()()()()()()()()(())()()(())()()()()()(())()()"

    Returns: 374

  78. "(()()()((()))()())"

    Returns: 77

  79. "()((())(((((()(((((()())((()(((()))())))))))))))))"

    Returns: 338

  80. "()()()()(()())()(()(())())()(())()(())()()()"

    Returns: 339

  81. "(())()(())()((())()((())))(())((()))(())()(()())"

    Returns: 300

  82. "(())((())((()(()(((()(((()))))))))))"

    Returns: 167

  83. "()(((((((((()(())(()(()(()(((())))))))))))))))"

    Returns: 268

  84. "((()()((())((())))))(()())"

    Returns: 98

  85. "(())()()()()()()()(())()()()()()()()()(())()()()"

    Returns: 396

  86. "()(())()()()()(())()()()()()()()()(())"

    Returns: 227

  87. "(((()((((((()()(((((((((((()))))))))))))))))))))"

    Returns: 175

  88. "()()()()()()()()()()(())()()()(())()()((()))()()()"

    Returns: 428

  89. "((((((((((((((((((((((()))))))))))))))))))))))"

    Returns: 43

  90. "()()()()()()()()()()()()()()()()"

    Returns: 120

  91. "(((((((()((((((((((((((((())))))))))))))))))))))))"

    Returns: 93

  92. "()((((((((()))))))))"

    Returns: 24

  93. "()(((()(()((((()((((((()(((((())))))))))))))))))))"

    Returns: 249

  94. "()()()(())()()(()()()())()()()()()(()())()()()()()"

    Returns: 480

  95. "()()()()()()()()()()()()()()()(())()()()()()()()()"

    Returns: 420

  96. "((()((()(()(((((((()))))))))))))"

    Returns: 113

  97. "()(())()()()()()()()()()()()()()()()()()()()()"

    Returns: 273

  98. "((()))"

    Returns: 3

  99. "()()()()()()()()()()()()()(())()()()(())()()()()()"

    Returns: 436

  100. "(((((((((((()((())))))))))))))"

    Returns: 53

  101. "((()(()))((()()())(((()((())))((()()()())(()))))))"

    Returns: 540

  102. "()()()()()()()()()()()()()()()()()()()()()()()()()"

    Returns: 300

  103. "(((((((((((((((((((((((())))))))))))))))))))))))"

    Returns: 45

  104. "((((((()(())((())))(()(())((())))()((((())))))))))"

    Returns: 368

  105. "(())(())(())(())((()))((()()))(())(())(())(())(())"

    Returns: 281

  106. "((((()))))(()()((())()))"

    Returns: 72

  107. "(()()(()))"

    Returns: 17

  108. "()()((())())()()()()()()((((()))))()()()"

    Returns: 235

  109. "(()(()(()(()(()(()(()(()())())())())())())())())"

    Returns: 704

  110. "()(()()()()((()))())()(()())()((())())(()(()(())))"

    Returns: 414

  111. "(())()(()((())))()(())()()()(()())()((()()()))()()"

    Returns: 394

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: