Statistics

Problem Statement for "BlockCounter"

Problem Statement

You are given a compressed word that is in one of the following three forms:

  1. A single character 'A' or 'B'. In this case, the uncompressed word is equal to the compressed one.
  2. A string formatted as "ST" (quotes for clarity), where S and T are each compressed words. To uncompress a word of this form, uncompress S and T and return their concatenation.
  3. A string formatted as "(X,S)" (quotes for clarity), where X is a digit between 1 and 9, inclusive, and S is a compressed word. To uncompress a word of this form, uncompress S and return the concatenation of X copies of that uncompressed word.

For example, "(2,A(3,AB))" uncompresses to "AABABABAABABAB", and "A(2,B)" uncompresses to "ABB". The latter example is uncompressed as follows:

  1. "A(2,B)" is in form 2, where S = "A" and T= "(2,B)". S is in form 1 so it's already uncompressed. Next, we uncompress T.
  2. "(2,B)" is in form 3, where X = 2 and S = "B". S is in form 1 so it's already uncompressed. We concatenate 2 copies of it to get "BB".
  3. We concatenate S and T from step 1 to get "ABB".

A maximal continuous sequence of the same letter in a word is called a block. For example, "AABAAABBBAA" contains 5 blocks: AA, B, AAA, BBB, and AA.

You are given a compressed word. Return the number of blocks in the uncompressed form of the word.

Definition

Class:
BlockCounter
Method:
countBlocks
Parameters:
String
Returns:
long
Method signature:
long countBlocks(String word)
(be sure your method is public)

Constraints

  • word will contain between 1 and 50 characters, inclusive.
  • word will contain only parenthesis '(', ')', digits '1'-'9', letters 'A' and 'B' and commas ','.
  • word will be formatted as described in the problems statement.

Examples

  1. "(2,A(3,AB))"

    Returns: 12

    The example from the problem statement.

  2. "A(1,A)A(5,AAA)"

    Returns: 1

    In this case the word uncompresses to a string of 18 'A'-s.

  3. "B(3,A)"

    Returns: 2

  4. "ABA(2,ABA)(3,ABA)"

    Returns: 13

  5. "(2,B)BABABA"

    Returns: 6

  6. "(2,B)ABABA"

    Returns: 6

  7. "(3,(2,(1,AB)))B"

    Returns: 12

  8. "(3,(2,(1,ABA)))B"

    Returns: 14

  9. "A(8,AA(3,B))"

    Returns: 16

  10. "(9,(9,(9,(9,(9,(9,(9,(9,(9,(9,(9,(9,AB))))))))))))"

    Returns: 564859072962

  11. "A"

    Returns: 1

  12. "AB"

    Returns: 2

  13. "BBB"

    Returns: 1

  14. "ABBB"

    Returns: 2

  15. "(8,B)"

    Returns: 1

  16. "AAAAA"

    Returns: 1

  17. "A(5,A)"

    Returns: 1

  18. "(7,BB)"

    Returns: 1

  19. "(4,B)A"

    Returns: 2

  20. "ABABBB"

    Returns: 4

  21. "BA(2,A)"

    Returns: 2

  22. "B(4,AB)"

    Returns: 9

  23. "(2,BBA)"

    Returns: 4

  24. "A(5,B)B"

    Returns: 2

  25. "(9,BA)A"

    Returns: 18

  26. "(5,B)AA"

    Returns: 2

  27. "BBBAAAB"

    Returns: 3

  28. "BBA(7,A)"

    Returns: 2

  29. "BA(6,BA)"

    Returns: 14

  30. "A(2,ABA)"

    Returns: 5

  31. "(6,AAAA)"

    Returns: 1

  32. "BA(2,A)B"

    Returns: 3

  33. "B(2,BA)A"

    Returns: 4

  34. "(7,AAA)B"

    Returns: 2

  35. "B(8,B)BA"

    Returns: 2

  36. "(6,AB)BA"

    Returns: 13

  37. "(7,A)BBB"

    Returns: 2

  38. "BAAABBAB"

    Returns: 5

  39. "(5,(9,B))"

    Returns: 1

  40. "BBBB(4,B)"

    Returns: 1

  41. "ABB(9,AB)"

    Returns: 20

  42. "AA(1,BBA)"

    Returns: 3

  43. "B(2,AABA)"

    Returns: 6

  44. "(4,AAAAB)"

    Returns: 8

  45. "BBA(7,B)A"

    Returns: 4

  46. "AA(1,BB)B"

    Returns: 2

  47. "B(2,ABB)B"

    Returns: 5

  48. "(8,BAAA)B"

    Returns: 17

  49. "BA(4,B)AB"

    Returns: 5

  50. "B(8,BA)AB"

    Returns: 17

  51. "(3,AAB)BB"

    Returns: 6

  52. "B(4,B)BBA"

    Returns: 2

  53. "(9,BA)ABB"

    Returns: 19

  54. "(3,B)BAAB"

    Returns: 3

  55. "ABABBBAAA"

    Returns: 5

  56. "A(1,(5,A))"

    Returns: 1

  57. "(4,B(7,B))"

    Returns: 1

  58. "(7,(2,AA))"

    Returns: 1

  59. "(1,(8,A)B)"

    Returns: 2

  60. "(4,A)(7,A)"

    Returns: 1

  61. "BBBBA(7,B)"

    Returns: 3

  62. "AABB(5,BB)"

    Returns: 2

  63. "ABB(7,BAB)"

    Returns: 16

  64. "AB(9,AABB)"

    Returns: 20

  65. "B(3,AAABA)"

    Returns: 8

  66. "(9,BABAAB)"

    Returns: 37

  67. "(2,(1,A))B"

    Returns: 2

  68. "ABBA(8,B)A"

    Returns: 5

  69. "AAB(4,BB)A"

    Returns: 3

  70. "AB(8,BAB)B"

    Returns: 18

  71. "B(9,BBBA)B"

    Returns: 19

  72. "(6,BAAAB)A"

    Returns: 14

  73. "BBA(6,B)AA"

    Returns: 4

  74. "AA(9,BA)BA"

    Returns: 21

  75. "B(3,AAB)AA"

    Returns: 8

  76. "(8,AABB)AB"

    Returns: 18

  77. "AA(9,B)BAA"

    Returns: 3

  78. "B(6,AA)ABB"

    Returns: 3

  79. "(2,AAA)BAB"

    Returns: 4

  80. "A(8,B)AAAB"

    Returns: 4

  81. "(2,AB)BABA"

    Returns: 7

  82. "(2,B)BAABB"

    Returns: 3

  83. "AABAABBAAA"

    Returns: 5

  84. "(2,(1,(8,(4,A))))"

    Returns: 1

  85. "(4,B)"

    Returns: 1

  86. "B(2,A)"

    Returns: 2

  87. "(8,(5,(9,(6,B))))"

    Returns: 1

  88. "AA(1,A)(7,A)(3,(2,A(5,A)(6,(7,(5,(5,(3,B)))))))"

    Returns: 12

  89. "A(4,BA)(6,B)"

    Returns: 10

  90. "B(4,A)A"

    Returns: 2

  91. "(8,B)(9,A)B"

    Returns: 3

  92. "B(9,A)AAABBA(2,A)BBB"

    Returns: 5

  93. "(2,(1,(9,A)))"

    Returns: 1

  94. "(9,(4,(1,(6,(5,(5,A))))))"

    Returns: 1

  95. "(4,(2,(8,(8,(7,A)A)))(2,A)(9,B(4,(1,(7,A)))))"

    Returns: 73

  96. "(8,(6,B)(6,(9,(8,A(4,(6,B)))))(2,A))"

    Returns: 6928

  97. "(9,A)A(8,BABA)"

    Returns: 33

  98. "(5,(6,(9,(3,(6,(6,B))))))"

    Returns: 1

  99. "BAAAAAAABBB(1,B(1,B)ABAABABA)"

    Returns: 10

  100. "(6,AA)(3,B)ABB(8,A)(1,A)AAB(3,A)A"

    Returns: 7

  101. "(4,A)(9,(6,(5,B)))"

    Returns: 2

  102. "(8,(9,(3,(9,A)A(3,(3,A)(4,(7,(1,(8,B))))))A))"

    Returns: 1297

  103. "BA(9,B(5,(8,(1,A)B)(2,A)))"

    Returns: 740

  104. "(7,(2,AB(5,(8,(5,A)B))))"

    Returns: 1148

  105. "(2,(2,(7,(9,(8,B))B))B)"

    Returns: 1

  106. "(4,(2,(3,(1,(7,(2,(7,B)(1,(8,(1,(4,A))))))))))"

    Returns: 672

  107. "(6,(2,A)(6,(1,(4,(9,(3,A))))))"

    Returns: 1

  108. "(4,B(5,(4,A))AA(2,A)B)(6,A)"

    Returns: 10

  109. "(4,A)(8,(9,(7,(1,(5,(8,A)A))BBA)))"

    Returns: 1009

  110. "(2,(4,(6,(9,(1,(3,BBB)A)A))))"

    Returns: 864

  111. "(8,(8,(3,(8,(5,(4,(7,(4,B)))))(2,(4,B)))))"

    Returns: 1

  112. "(6,(4,(1,A)))(5,(9,(6,(8,(3,A)))))"

    Returns: 1

  113. "AA(5,A(3,AB)(1,(5,ABBB(3,(8,B))))B)(2,(3,A))B"

    Returns: 82

  114. "(2,(5,(4,(6,(6,(3,(9,(6,B))))))))"

    Returns: 1

  115. "(5,A)ABA(7,(4,(7,A)))(7,(5,B)A)AB"

    Returns: 18

  116. "(3,BBB(1,(8,(3,(4,(7,(6,A))))))(9,B))"

    Returns: 7

  117. "(8,(7,B(8,(9,(2,A))(3,(8,(8,(7,B)))(4,A)))))"

    Returns: 2800

  118. "(7,A)A(3,(9,(5,B)(6,B)))B(1,(2,A)B)"

    Returns: 4

  119. "(4,(7,(8,(5,A(5,AA)(3,(2,B))(2,A)B))))B"

    Returns: 4480

  120. "ABBBAAAABAABBBBAAABBBAAAAABAABABAAABBBAAAA"

    Returns: 17

  121. "(1,(3,(4,(3,(2,(5,(3,(6,(4,B)))(9,A)B)BB)))))"

    Returns: 721

  122. "B(1,A(8,B)(4,(3,A))(4,(7,(7,A)ABB(4,A))BA))"

    Returns: 68

  123. "(4,(4,(3,B(6,(6,A))(5,B))B)(1,(3,(8,B))))"

    Returns: 97

  124. "(9,B(2,A)(8,BB(3,(1,(2,B)BA(4,A)(9,A))))AB)"

    Returns: 451

  125. "(3,(7,(2,(5,(8,A(7,(9,(5,(4,(1,(1,B)))))))))))"

    Returns: 3360

  126. "(8,(4,(5,(8,(9,(8,(4,(8,(8,(9,(6,(7,A)))))B)))))))"

    Returns: 737280

  127. "(5,(6,(2,(4,(8,A)))(7,(6,(7,(1,(5,A)))))))"

    Returns: 1

  128. "B(2,(1,(8,A(4,B)(6,(7,A)A)(8,BB)))(2,B)A)"

    Returns: 66

  129. "(8,(5,(6,A))(3,(3,B(4,A))BBBBB)(8,A))(3,A)"

    Returns: 161

  130. "(1,(3,(2,(9,(8,B)))))(6,(7,(1,(4,(8,A)))))"

    Returns: 2

  131. "(7,A)(2,(6,(3,(2,(9,(4,(6,(8,B))))))))(6,B)"

    Returns: 2

  132. "(6,(1,(1,(1,(9,(2,(3,(5,(3,(8,(3,(7,B))))))))))))"

    Returns: 1

  133. "(3,(7,(5,A)))(6,(1,(8,(7,(5,(2,(9,(2,B))))))))"

    Returns: 2

  134. "(4,A(1,(7,A)(6,(8,(7,BB)A))))(9,(7,A))AA"

    Returns: 385

  135. "(2,(8,(3,(2,B)(6,(4,(2,(1,(8,A)))))A))(4,(3,A)))"

    Returns: 96

  136. "(9,(1,(8,(2,(3,(6,(1,(7,B)))))(1,(7,A)))))"

    Returns: 144

  137. "(1,(9,(1,B(1,B))))A(1,A)(6,(2,B)BB)(2,A)"

    Returns: 4

  138. "BA(5,BBA(9,(3,A))(7,BB(4,B)(5,A)B)ABAA(6,B)BBBA)"

    Returns: 112

  139. "(3,B)BB(8,A(4,A))(9,(4,(4,(1,AB)AA)(4,B)))(2,B)B"

    Returns: 361

  140. "(3,(8,(1,B)))(1,(1,(7,(6,(2,(6,B))))))(2,B)(2,B)"

    Returns: 1

  141. "AAB(6,B)(5,BAAA(5,A)(2,AB)B)A(5,(6,AA)(5,B))AA"

    Returns: 33

  142. "(5,(8,(2,(9,(5,B)(9,(6,BB)))))(1,B))(9,B)A(3,B)"

    Returns: 3

  143. "A(6,(7,A))(6,A)(7,(1,(2,(1,(6,A))))A)(2,B)AA"

    Returns: 3

  144. "(8,(8,(8,(7,(9,(7,(8,(9,(8,(8,(7,B)))))))))))"

    Returns: 1

  145. "(9,(8,(7,A)(8,(8,(9,(7,(8,(8,(8,A)))))))))"

    Returns: 1

  146. "(9,(9,A(9,(9,(9,(9,(8,(8,A))))))BB)BBB(7,A))"

    Returns: 163

  147. "(8,(8,(9,(8,(7,(8,(9,(9,(7,(9,(7,B)))))(7,A)))))))"

    Returns: 516096

  148. "(9,(7,(8,(7,(7,(9,(7,(8,A))))(9,(9,A))))))"

    Returns: 1

  149. "(7,(7,(7,(8,(7,(9,(8,(8,(8,(8,B)))))))A)))"

    Returns: 686

  150. "(8,(9,(9,(8,(8,(8,(8,B)))))(8,(7,(7,A))))(7,B))"

    Returns: 145

  151. "(9,(9,B(7,B)))(9,BA(9,(8,(8,A)(9,B)))(9,A))"

    Returns: 1314

  152. "(9,(8,(8,(9,(7,(8,A))))))(8,(9,B)A)(9,AB)"

    Returns: 34

  153. "(9,(7,(8,B)(8,(8,A(8,B)B(7,(8,(8,(9,(9,AB)))))))))"

    Returns: 292634497

  154. "(8,B)(8,(9,(9,(7,A))))(9,(9,B))(9,A)(8,A)"

    Returns: 4

  155. "(7,(8,(9,(8,(7,(9,(8,(8,(8,(9,A))))))))))"

    Returns: 1

  156. "(7,(9,B(8,B)BA(7,(8,(7,(7,B))AA))(8,B)B))"

    Returns: 7183

  157. "(9,BB(7,(9,B(8,A))(8,A)))(9,B(8,(9,(8,A)))B)"

    Returns: 1153

  158. "(9,(9,(7,(7,(9,(8,(8,(8,A(7,B))))))))(9,A))"

    Returns: 36578305

  159. "(9,(8,B))(9,(9,(7,(9,A)))(7,B))(8,(8,B))BABB"

    Returns: 21

  160. "(9,(7,(9,(9,(8,(9,(8,(8,(9,(9,(9,AB)))))))))))"

    Returns: 34284321792

  161. "(9,A(8,(8,BB))(9,(9,AA(7,A)B(7,B)AAB))A)"

    Returns: 2935

  162. "AA(7,(9,A)B)ABBABBBBABBBA(7,A)ABB(9,A)B(7,A)ABAB"

    Returns: 28

  163. "BBAA(7,ABB)BB(7,A(7,B)AB)(9,BB)ABAA(8,A)B"

    Returns: 47

  164. "(9,(8,(7,(7,(9,(9,(7,(7,(8,(7,(9,(9,AB))))))))))))"

    Returns: 127031877504

  165. "(8,(7,(8,(9,(8,(9,(9,(7,(8,(8,AB))))))))))"

    Returns: 2341011456

  166. "(8,(7,(9,(9,(7,(7,(9,(7,AB))))))(8,(8,(9,AB)))))"

    Returns: 28069776

  167. "(7,(9,(7,(7,AB)))(8,(9,AB)(9,(8,(9,(8,AB))))AB))"

    Returns: 587902

  168. "(9,AB(8,(8,AB)(7,(8,(9,(9,(7,(8,AB))AB))))))"

    Returns: 37232658

  169. "(7,(9,AB))AB(8,(9,(7,(8,(7,(9,(9,(8,AB))))))))"

    Returns: 36578432

  170. "(9,(8,(7,(9,(8,(7,(8,(9,(9,(9,(9,AB)))))))))))"

    Returns: 26665583616

  171. "(8,(8,(8,(8,(7,(8,(9,(7,(9,(7,(7,(8,AB))))))))))))"

    Returns: 101964054528

  172. "(8,AB(9,(9,(8,AB)AB)(9,ABAB))(9,(8,AB))AB)"

    Returns: 15440

  173. "(8,ABAB)(9,(8,(9,AB)ABABAB))ABABAB(9,AB)"

    Returns: 1784

  174. "AB(8,(8,(9,(8,(8,(9,AB)))))AB)(8,(8,AB)AB)"

    Returns: 663714

  175. "AB(7,(7,(7,(9,AB)))ABABAB(9,AB))ABABABAB"

    Returns: 6352

  176. "(8,(7,(9,AB(9,(9,(8,(8,AB)))))ABABABAB))"

    Returns: 5226928

  177. "(7,(7,(7,(7,(9,(8,(9,(8,(7,(9,(7,AB)))))))))))"

    Returns: 10978063488

  178. "ABAB(7,(9,AB)(7,AB))ABABAB(7,AB)ABABABABAB"

    Returns: 258

  179. "(9,(9,AB)(8,(8,AB))AB(7,ABAB)AB)(7,ABAB)"

    Returns: 1630

  180. "(7,(7,(7,(7,(7,ABAB)(9,(9,(7,AB)))AB)AB)))"

    Returns: 2795450

  181. "(9,(9,(8,(9,(7,(9,ABAB(7,(9,ABAB))))))))"

    Returns: 94058496

  182. "ABABABABABABABABABABABABABABABABABABABABABABABABAB"

    Returns: 50

  183. "(8,AB)(9,ABABABABABABABABABABABABABABABABAB)"

    Returns: 322

  184. "(9,(9,(9,(9,(9,(9,(9,(9,(9,(9,(9,ABA)))))))))))"

    Returns: 62762119219

  185. "A(9,(9,(9,(9,(9,(9,ABBB(9,(9,(9,(9,A))))))))))"

    Returns: 1062883

  186. "(9,(9,(9,(9,(9,(9,(9,(9,(9,(9,(9,(9,A))))))))))))"

    Returns: 1

  187. "(9,A(9,A(9,A(9,A(8,B(9,BB(8,A(9,A(9,A)))))))))"

    Returns: 944785

  188. "(9,(9,(9,(9,(9,(9,(9,(9,(9,(9,(9,(9,BA))))))))))))"

    Returns: 564859072962

  189. "(9,(9,(9,(9,(9,(9,(9,(9,(9,(9,ABBABA))))))))))"

    Returns: 13947137605

  190. "A(9,B(9,A(9,(9,A(9,B(9,A(9,(9,(9,B(9,ABA))))))))))"

    Returns: 7748527897

  191. "(9,(9,(9,B(9,(9,(9,(9,(9,A)(9,(9,AB))(9,A))))A))))"

    Returns: 774842436

  192. "AAA(9,(9,(9,(9,(9,(9,(9,(9,(9,(9,AB))))))))))BBB"

    Returns: 6973568802

  193. "(8,(9,(9,(9,(9,(9,(9,AB(9,(9,(9,(9,AB))B)A))))))))"

    Returns: 55797053473

  194. "(9,(9,(9,(9,(9,(9,(9,(9,(9,(9,(9,AAABBB)))))))))))"

    Returns: 62762119218

  195. "B(9,(9,(9,(9,(9,(9,(9,(9,(9,(9,(9,(9,A))))))))))))"

    Returns: 2

  196. "(9,(9,(9,(9,(9,(9,(9,(9,(9,A)))))))))"

    Returns: 1

  197. "(9,(9,(9,(9,(9,(9,(9,(9,(9,(9,(9,AB)))))))))))"

    Returns: 62762119218

  198. "B(9,(9,(9,(9,(9,(9,(9,(9,(9,(9,(9,AB)))))))))))A"

    Returns: 62762119220

  199. "(9,A(9,A(9,A(9,A(9,A(9,B(9,B(9,B))))))))(9,A)"

    Returns: 118099

  200. "AB(1,A)"

    Returns: 3

  201. "(9,AB)A(9,AB)"

    Returns: 36

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: