TopCoder problem "RunLengthPlus" used in TCCC05 Wildcard (Division I Level One)



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

Definition

    
Class:RunLengthPlus
Method:compress
Parameters:String
Returns:String
Method signature:String compress(String s)
(be sure your method is public)
    
 

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"

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=3961

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=6553&pm=3961

Writer:

lars2520

Testers:

PabloGilberto , Yarin , vorthys

Problem categories:

Dynamic Programming, Encryption/Compression, String Manipulation