RunLengthPlus
TCCC05 Wildcard · 2005-01-10 · by lars2520
TCCC05 Wildcard · 2005-01-10 · by lars2520 · Dynamic Programming, Encryption/Compression, String Manipulation
Problem Statement
Problem Statement
One type of compression is run length encoding. In this case, a character may be preceded by an integer N, which indicates that the character should be repeated N times. For example, the String "3ABBC10D" would be decompressed as "AAABBCDDDDDDDDDD". A character that is not preceded by an integer is repeated just once. We are going to enrich this slightly be allowing a sequence of characters to be preceded by an integer N, indicating that the sequence should be repeated N times. In this case, the sequence of characters should be surrounded by parentheses. Additionally, you may nest the compressed sequences. Thus, the compressed sequence "X2(2A3(BC))X" would be decompressed as "XAABCBCBCAABCBCBCX". You will be given a String of uppercase letters and are to compress it in such a way that the result has as few characters as possible. If there are multiple ways to do this, choose the one that comes first lexicographically (using standard ASCII ordering).
Constraints
- s will contain between 1 and 50 uppercase letters, inclusive.
Examples
0)
"AAABBCDDDDDDDDDD" Returns: "3A2BC10D"
1)
"XAABCBCBCAABCBCBCX" Returns: "X2(2A3(BC))X"
2)
"ABCBACBABCBABCABACACBCBABACBCBBABACBACBCACBBAC" Returns: "ABCBA2(CBAB)CABACACBCBABACBC2BA2(BAC)BCAC2BAC"
3)
"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA" Returns: "50A"
4)
"XXXXXSSSSQQPMMGGGIIIIIIPMMGGGIIIIIIPMMGGGIIIIII" Returns: "5X4S2Q3(P2M3G6I)"
Submissions are judged against all 83 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class RunLengthPlus with a public method string compress(string s) · 83 test cases · 2 s / 256 MB per case