Statistics

Problem Statement for "RunLengthPlus"

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

  1. "AAABBCDDDDDDDDDD"

    Returns: "3A2BC10D"

  2. "XAABCBCBCAABCBCBCX"

    Returns: "X2(2A3(BC))X"

  3. "ABCBACBABCBABCABACACBCBABACBCBBABACBACBCACBBAC"

    Returns: "ABCBA2(CBAB)CABACACBCBABACBC2BA2(BAC)BCAC2BAC"

  4. "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

    Returns: "50A"

  5. "XXXXXSSSSQQPMMGGGIIIIIIPMMGGGIIIIIIPMMGGGIIIIII"

    Returns: "5X4S2Q3(P2M3G6I)"

  6. "AABBAABBAABBAABBAABBAAAAAAAAAAAAAAAAAAAAA"

    Returns: "5(2A2B)21A"

  7. "AAAAACCAAAAABBBAAAAAABBBAAAAAABBBAAAAAABBBA"

    Returns: "5A2C4(5A3BA)"

  8. "BBBBDDDDDCCCDBBBBDDDDBBBBBDDDDBBBBBDDDDBBBBBDDDDB"

    Returns: "4B5D3CD4(4B4DB)"

  9. "DDDBBBBBBAABCABCBBBBAABCABCBBBBAABCABCBBBBAABCABC"

    Returns: "3D2B4(4B2ABCABC)"

  10. "EEEEEDDFEEEEEDDFEEEEEDDFEEEEEDDFEEEEEDDFFF"

    Returns: "5(5E2DF)2F"

  11. "DDDFDDDFDDDFCACACABCACACABCACACABCACACABCACACABCD"

    Returns: "3(3DF)5(3(CA)B)CD"

  12. "FFFHHHHHGGBGGBGGBHHGGBGGBGGBHHGGBGGBGGBHHGGBGGBGGB"

    Returns: "3F3H4(2H3(2GB))"

  13. "DDDDAAGGDDDDAAGGDDDDAAGGDDDDAAGGDDDDAAGGFFFF"

    Returns: "5(4D2A2G)4F"

  14. "CCCCAAAAEEEEAAEEEEAAEEEEAAAAAAEEEEAAEEEEAAEEEEAA"

    Returns: "4C2(4A3(4E2A))"

  15. "EEEEEJCCJCCJCCJCCBBBJCCJCCJCCJCCBBBJCCJCCJCCJCCBBB"

    Returns: "5E3(4(J2C)3B)"

  16. "GGAAGGAACCGGAAGGAACCGGAAGGAACCGGAAGGAACCJJ"

    Returns: "4(2(2G2A)2C)2J"

  17. "GGDGGDAAGGDGGDAAGGDGGDAAGGDGGDAAGGDGGDAAF"

    Returns: "5(2(2GD)2A)F"

  18. "CCCCHHHCCCCHHHCCCCHHHCCCCHHHNNNNHHHNNNNHHH"

    Returns: "4(4C3H)2(4N3H)"

  19. "KNAAAGGAAAGGAAAGGNAAAGGAAAGGAAAGGNAAAGGAAAGGAAAGG"

    Returns: "K3(N3(3A2G))"

  20. "JJJJJJJJJJJJKJJJJJJJJJJJJKJJJJJJJJJJJJKMMMMMCC"

    Returns: "3(12JK)5M2C"

  21. "QQQLLQQQLLQQQLLQQQLLQQQLLCCCCFFFFNNNNEEEE"

    Returns: "5(3Q2L)4C4F4N4E"

  22. "FFAAAARAAAARFFAAAARAAAARFFAAAARAAAARGGGGJGGGGJ"

    Returns: "3(2F2(4AR))2(4GJ)"

  23. "IAIACCCIAIACCCIAIACCCIAIACCCIAIACCCNNNNK"

    Returns: "5(IAIA3C)4NK"

  24. "MMMMAAASAAASAAASPAAASAAASAAASPAAASAAASAAASPCCC"

    Returns: "4M3(3(3AS)P)3C"

  25. "BQQAIIIIIIIIIIIIIIAIIIIIIIIIIIIIIAIIIIIIIIIIIIII"

    Returns: "B2Q3(A14I)"

  26. "AAAEEEQEEEQEEEQEEEQEEEQIIEEEQEEEQEEEQEEEQEEEQII"

    Returns: "3A2(5(3EQ)2I)"

  27. "DDCDDCSWWDDCDDCSWWDDCDDCSWWDDCDDCSWWNNNN"

    Returns: "4(2(2DC)S2W)4N"

  28. "EEEEEDDEEEEEDDEEEEEDDWBBKKKBBKKKBBKKKBBKKK"

    Returns: "3(5E2D)W4(2B3K)"

  29. "HHHHWWWRWWWRWWWRAWWWRWWWRWWWRAWWWRWWWRWWWRA"

    Returns: "4H3(3(3WR)A)"

  30. "QQQGGGYYGGGYYGGGYYGGGYYYGGGYYGGGYYGGGYYGGGYYY"

    Returns: "3Q2(4(3G2Y)Y)"

  31. "AAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB"

    Returns: "3A45B"

  32. "AAAAACCCCCACAAAAACCCCCACAAAAACCCCCACAAAAACCCCCACB"

    Returns: "4(5A5CAC)B"

  33. "CBBBCBBBCBBBCBBBCBBBCCCCBBBCCCCBBBCCCCBBBCCCCBBB"

    Returns: "5(C3B)4(4C3B)"

  34. "BBBBDDDBBBBDDDBBBBDDDBEBEBEBEBEDDBEBEBEBEBEDD"

    Returns: "3(4B3D)2(5(BE)2D)"

  35. "CCCCCEEFFCCCCCEEFFCCCCCEEFFCCCCCEEFFCCCCCEEFFAAA"

    Returns: "5(5C2E2F)3A"

  36. "AAABBBAAABBBAAABBBAAABBBAAABBBEEEEEGGGGDEDE"

    Returns: "5(3A3B)5E4GDEDE"

  37. "HHAAGGAAGGHHAAGGAAGGHHAAGGAAGGHHAAGGAAGGEEE"

    Returns: "4(2H2(2A2G))3E"

  38. "EEEBEEEBEEEBEEEBEEEBDDDEEEBEEEBEEEBEEEBEEEBDDDE"

    Returns: "2(5(3EB)3D)E"

  39. "DDFCFCFCDDFCFCFCDDFCFCFCDDFCFCFCDDFCFCFCHH"

    Returns: "5(2D3(FC))2H"

  40. "JJJJJJJJJJJJJJJJJJJJAJJJJJJJJJJJJJJJJJJJJAHHHH"

    Returns: "2(20JA)4H"

  41. "LLJJJLLJJJLLJJJLLJJJBLAALAALAABLAALAALAA"

    Returns: "4(2L3J)2(B3(L2A))"

  42. "FFFFGGMKKMKKMKKGGMKKMKKMKKGGMKKMKKMKKGGMKKMKKMKK"

    Returns: "4F4(2G3(M2K))"

  43. "KKKJKKKJKKKJMMNAAAAAKKHAAAAAKKHNAAAAAKKHAAAAAKKH"

    Returns: "3(3KJ)2M2(N2(5A2KH))"

  44. "BBBOHOHKKOHOHKKBBBOHOHKKOHOHKKJJJHHHJJJHHHJJJHHH"

    Returns: "2(3B2(OHOH2K))3(3J3H)"

  45. "MMMMALGGGDGGGDALGGGDGGGDALGGGDGGGDALGGGDGGGD"

    Returns: "4M4(AL2(3GD))"

  46. "KKKKKGGGQGGGQKKKKKGGGQGGGQDDDDFFFDDDDFFFDDDDFFF"

    Returns: "2(5K2(3GQ))3(4D3F)"

  47. "MMMMMIIMMMMMIIDDDDJJMMMMMIIMMMMMIIDDDDJJQQQQEEE"

    Returns: "2(2(5M2I)4D2J)4Q3E"

  48. "OOKOOKOOKOOKIOOKOOKOOKOOKIOOKOOKOOKOOKIG"

    Returns: "3(4(2OK)I)G"

  49. "DCPPPPMPPPPMDCPPPPMPPPPMTTTTBBBTTTTBBBTTTTBBB"

    Returns: "2(DC2(4PM))3(4T3B)"

  50. "TDDDJJJJJJJJJJJJKKKMKKKMKKKMOKKKMKKKMKKKMO"

    Returns: "T3D12J2(3(3KM)O)"

  51. "RBRBRBRBRBMMRBRBRBRBRBMMRBRBRBRBRBMMLKKVLKKV"

    Returns: "3(5(RB)2M)2(L2KV)"

  52. "NNNNNTNNNNNTNNNNNTIIINNNNNTNNNNNTNNNNNTIIIQ"

    Returns: "2(3(5NT)3I)Q"

  53. "RLLLLLLLLLLLLRLLLLLLLLLLLLRLLLLLLLLLLLLSSS"

    Returns: "3(R12L)3S"

  54. "IIIIIQAAIIIIIQAAIIIIIQAAIIIIIQAAIIIIIQAAYYY"

    Returns: "5(5IQ2A)3Y"

  55. "WWWWWQSSSEESSSEEQSSSEESSSEEQSSSEESSSEEQSSSEESSSEE"

    Returns: "5W4(Q2(3S2E))"

  56. "AAABBBBBBBBBBAABBBBBBBBBBAABBBBBBBBBBAABBBBBBBBBB"

    Returns: "A4(2A10B)"

  57. "CCBBBBCCCCCACCCCCACCCCCAABBBBCCCCCACCCCCACCCCCAA"

    Returns: "2C2(4B3(5CA)A)"

  58. "CCCCDCCCCDCCCCDCCCCDDDCCCCDCCCCDCCCCDCCCCDDDDD"

    Returns: "2(4(4CD)2D)2D"

  59. "EAEAEEEEDDDDCDDDDCEEEEDDDDCDDDDCEEEEDDDDCDDDDC"

    Returns: "EAEA3(4E2(4DC))"

  60. "EEEEECCCEEEEECCCEEEEECCCEEEEECCCEEEEECCCEE"

    Returns: "5(5E3C)2E"

  61. "BBBBDBBBBDBBBBDEBBBBDBBBBDBBBBDEBBBBDBBBBDBBBBDEB"

    Returns: "3(3(4BD)E)B"

  62. "CFCFCFCFCFAHCFCFCFCFCFAHCFCFCFCFCFAHHHEE"

    Returns: "3(5(CF)AH)2H2E"

  63. "GGGCIIDIIDIIDGGGCIIDIIDIIDGGGCIIDIIDIIDIIII"

    Returns: "3(3GC3(2ID))4I"

  64. "IDDDIDDDIDDDIDDDIIIIIDDDEEIIIIIDDDEEIIIIIDDDEE"

    Returns: "4(I3D)3(5I3D2E)"

  65. "BBBBIIIDDDDBDDDDBIIIDDDDBDDDDBIIIDDDDBDDDDBDDD"

    Returns: "4B3(3I2(4DB))3D"

  66. "BBIIIIEEEBBHIIIIEEEBBHIIIIEEEBBHIIIIEEEBBH"

    Returns: "2B4(4I3E2BH)"

  67. "BBBMMMMBMMMMBBBBMMMMBMMMMBBBBMMMMBMMMMBE"

    Returns: "3(3B2(4MB))E"

  68. "IIIJJIIIJJIIIJJIIIJJIIIJJCCCCCDCCCCCDCCCCCD"

    Returns: "5(3I2J)3(5CD)"

  69. "CCCCCEEECCCCCEEECCCCCEEECCCCCEEECCCCCEEEFF"

    Returns: "5(5C3E)2F"

  70. "LLLLPPPLLLLPPPLLLLPPPLLLLPPPAAAAAOAAAAAOAAAAAO"

    Returns: "4(4L3P)3(5AO)"

  71. "LLJEJEJEJEQQJEJEJEJEQQBBJEJEJEJEQQJEJEJEJEQQBB"

    Returns: "2L2(2(4(JE)2Q)2B)"

  72. "QQQQQAAAABHKHKKKHKHKKKHKHKKKHKHKKKHKHKKKBB"

    Returns: "5Q4AB5(HKH3K)2B"

  73. "DDLRRRRRGRRRRRGCCRRRRRGRRRRRGCCRRRRRGRRRRRGCC"

    Returns: "2DL3(2(5RG)2C)"

  74. "GGGGGGGGGGHGGGGGGGGGGHGGGGGGGGGGHGGGGGGGGGGHKKKIIC"

    Returns: "4(10GH)3K2IC"

  75. "KQQLLLKQQLLLKQQLLLKQQLLLKQQLLLTTTTTAAATTTTTAAA"

    Returns: "5(K2Q3L)2(5T3A)"

  76. "KRRKRRKRRKRRRRRKRRKRRKRRKRRRRRKRRKRRKRRKRRRRRKKK"

    Returns: "3(4(K2R)3R)3K"

  77. "VVVVVFVVVVVFVVVVVFVVVVVFVVVVVFFFFMMFFFMM"

    Returns: "5(5VF)2(3F2M)"

  78. "HDHDHDHDHDDDHDHDHDHDHDDDHDHDHDHDHDDDLLLL"

    Returns: "3(5(HD)2D)4L"

  79. "HHSSSSSQSSSSSQIIJJJJJBGJJJJJJBGJJJJJJBGJ"

    Returns: "2H2(5SQ)2I3(5JBGJ)"

  80. "CCCPPPPKKPPPPKKPPPPKKCCCPPPPKKPPPPKKPPPPKKUU"

    Returns: "2(3C3(4P2K))2U"

  81. "ABCABCAABCABCAAABCABCAABCABCAAA"

    Returns: "2(2(2(ABC)A)A)A"

  82. "RRRRRSSSSTSSSSTSSSSTSSSSTSSSSTSSSSTSSSSTSSSST"

    Returns: "5R8(4ST)"

  83. "ABCABCABCABCABCDEFGHABCDEFGH"

    Returns: "4(ABC)2(ABCDEFGH)"

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: