BlockCounter
TCCC07 Qual 2 · 2007-07-30 · by andrewzta
Problem Statement
You are given a compressed word that is in one of the following three forms:
- A single character 'A' or 'B'. In this case, the uncompressed word is equal to the compressed one.
- 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.
- 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:
- "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,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".
- 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.
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.
"(2,A(3,AB))" Returns: 12
The example from the problem statement.
"A(1,A)A(5,AAA)" Returns: 1
In this case the word uncompresses to a string of 18 'A'-s.
"B(3,A)" Returns: 2
"ABA(2,ABA)(3,ABA)" Returns: 13
"(2,B)BABABA" Returns: 6
Submissions are judged against all 201 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BlockCounter with a public method long long countBlocks(string word) · 201 test cases · 2 s / 256 MB per case