Statistics

Problem Statement for "CompressionText"

Problem Statement

You are part of a team that is working on a piece of software to handle text compression. Your team has designed the compression algorithm as follows:

To compress a given string of text, two strings, each 3 characters in length, will be chosen as compression keys. The strings may contain any combination of capital letters and/or spaces. Then, a compressed string will be generated from the original such that replacing "*1" in the compressed string with the first string and replacing "*2" with the second string will recreate the original text.

For example, if the two compression keys are "FOO" and "BAR", then the compressed string "*2X*1" would decompress to "BARXFOO", and "*1*1 *2" would decompress to "FOOFOO BAR".

You have been tasked with writing a proof of concept implementation to test the effectiveness of this compression scheme. You will be given a String original. Your goal is to optimally select the two compression keys, and generate the compressed text to be as short as possible. You are to return the length of the shortest possible text.

Definition

Class:
CompressionText
Method:
shortestLength
Parameters:
String
Returns:
int
Method signature:
int shortestLength(String original)
(be sure your method is public)

Constraints

  • original will contain between 1 and 50 characters, inclusive.
  • Each character of original will be an uppercase letter ('A'-'Z') or a space (' ').

Examples

  1. "BARXFOO"

    Returns: 5

    The first example from the problem statement.

  2. "FOOFOO BAR"

    Returns: 7

    The second example from the problem statement.

  3. "ABCDEFGHIJKLMNOPQRSTUVWXYABCDEFGHIJKLMNOPQRSTUVWXY"

    Returns: 46

    It's a long string, but no 3-character substring appears more than twice.

  4. "QWERTYUIOPASDFGHJKLZXCVBNM"

    Returns: 24

    Here, no substring repeats itself at all. The best we can do is to pick any two substrings to replace.

  5. "BBAAAABBBBAAABABABBBABABAAABABABAAABBAABABBBABAAAB"

    Returns: 40

  6. "AAA"

    Returns: 2

  7. "QJVEYIKAOCQCIAEYVTWMQGQNQDLUXHNFCQ"

    Returns: 32

  8. "EGGDKNPOWLJDXEXJTHSUHPLDXERNRBQCYPIPYJWNTNBJ"

    Returns: 41

  9. "ZDBTDYXLTIJNCMOLJZNJFTHA"

    Returns: 22

  10. "NOQVGHBYAZIKDNHYKFQXWBYSHEILRSBRFTKSCNBXF"

    Returns: 39

  11. "KKIEIXJSBWZQOYIDTNGMKSPBZ"

    Returns: 23

  12. "TOXPKPXKUKXLWWUHZTSVQIOUQBOSJNI"

    Returns: 29

  13. "KXZVHJSSQSLIORRLAZVDYWQL"

    Returns: 22

  14. "ZWLDFGGEDSKLLUOAQJJBGQQHWHQWUXVLUTSODSAFUMBOXYHCTB"

    Returns: 48

  15. "COPCXWMDBBFEEBPHIJQTRISOGUEDBNYZGRLDBPVJFUOV"

    Returns: 42

  16. "GWZCWWSUJVTHCJJZOKCGPBBWOUFZYUACYXNMSJDPKEKF"

    Returns: 42

  17. "JICHWNSIKCNHRIZOVBPQDSDXBJJYFGSDDGNITYHZJODHZPYSO"

    Returns: 47

  18. "AXZIUMTQENICMXPLLELFQOVTXCATKLYTMGWEANLHFSY"

    Returns: 41

  19. "ABEBGCCACAFGGCCDAEFGABAGDAADEADGCBAEC"

    Returns: 34

  20. "FCCDGCDCBFFEABBBBEGGCEDG"

    Returns: 22

  21. "DFFGCEGCFGACBE"

    Returns: 12

  22. "ACGAFEFADFGDCABAFBAAACGCCAGDGAEBBGBBEDGGDB"

    Returns: 39

  23. "KHMLNJMMNKHLIIIHHLNJIJIJIM"

    Returns: 23

  24. "HLKNJIIJHHKHMKNLLIIMNMIIJHLIH"

    Returns: 26

  25. "MHILHKNJLNMNLMLNJLJKNLHLLIKKLJNINJJJJLMIKNLH"

    Returns: 40

  26. "MNHMNMHMLILNHHHLMLJMIN"

    Returns: 20

  27. "UQRTSQOOPTQOUOUOURPTTPOPOPTQRUURPPTOTTPRRSSTUQ"

    Returns: 42

  28. "QOUQOPUURQPOPUURTRPPOOPOTQOQRRUTPRTSTPQRQTT"

    Returns: 40

  29. "UURUOPURUPPTROUOOROSPRURSRUPRUSSSQSQTUPPR"

    Returns: 37

  30. "USOQUTSOPUOSUTUPTOQPRPPPOSRUUOUUSTQPUTOORU"

    Returns: 40

  31. "JJJIIIIJIJJIJIJJJJIIJIIIJJJIIJJJIJJIJJIJIIIJJI"

    Returns: 35

  32. "LLKKKKKKLLKKLLKLLLLLKKLKKKKKKKLLKLLLKKKLKLLLKL"

    Returns: 36

  33. "JJJJJIJIIJJJIIJJIJJJJJJJJIIIIJIIIIIJJIIJJJJIIJIIII"

    Returns: 39

  34. "RRQRRQQQRRRQRQRQQRQRQRRQRRQRRRRRQRQRRRRRQRQQQQQQR"

    Returns: 39

  35. "IIHIHHHIHIHIHIIIHHHHHIIIIHHHIIIHHIHHHHIHHIIHII"

    Returns: 36

  36. "CDCCDDDCCCDDDCCCCCCDCDCDCCCCCCDDCCDDCDDCDCCDCCDD"

    Returns: 37

  37. "RSRSRSRRSSRRRSRSSSSRRRSSRSRSSSSSRSRRSRRSRRSRRSRSS"

    Returns: 38

  38. "HIIIHHHIIIIHHHHHHHHIIHHHHIHHIHIHIHHIHHHIHHHHII"

    Returns: 36

  39. "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

    Returns: 34

  40. "ABABA"

    Returns: 4

  41. "ABABAB"

    Returns: 4

  42. "ABABABA"

    Returns: 5

  43. "ABABABA"

    Returns: 5

  44. "ABABABAV"

    Returns: 6

  45. "Q O"

    Returns: 2

  46. "JTNMVCAVR B"

    Returns: 9

  47. "J FVSBPZLEZPGSJX"

    Returns: 14

  48. "YBHFJHKOHGZXPWEZSJGXAFFUBZDPYCQU"

    Returns: 30

  49. "ZRKAEAVURFTOBODEHKJHBXQPUFSNWPMNO"

    Returns: 31

  50. "QDBAMHALLJQX"

    Returns: 10

  51. "JFLZQDXIEKOIANNRVVTFWHR NO O"

    Returns: 26

  52. "XA UYLLYVNZ"

    Returns: 9

  53. "DCOXGTBN TOUEIYSSDAVB DTCPKWWQKTRHNWXUGWMT"

    Returns: 40

  54. "VIUS DROSTKOGPBFL"

    Returns: 15

  55. "EZAIKTDCERG"

    Returns: 9

  56. "QJREI PWYBRIZDKWIISAUXNEVVSZDRBWVGLYO"

    Returns: 35

  57. "UQZCRQJVH RIIDVXSPG COI"

    Returns: 22

  58. "RPFPZRL FEFKGNE"

    Returns: 13

  59. "BTPXZTWQOJOJVFYVHDJ VSXGC"

    Returns: 23

  60. "JHCGFNIZPM"

    Returns: 8

  61. "A"

    Returns: 1

  62. "BARXFOO"

    Returns: 5

  63. "ASDF"

    Returns: 3

  64. "AABBAABBBAABBA"

    Returns: 10

  65. "AAA"

    Returns: 2

  66. "E"

    Returns: 1

  67. "AA"

    Returns: 2

  68. "AAABB"

    Returns: 4

  69. "B"

    Returns: 1

  70. "ABCABCCABCAB"

    Returns: 8

  71. "ABC"

    Returns: 2

  72. " "

    Returns: 1

  73. "BABBBABBBBABBB"

    Returns: 10

  74. "DBDDEDBDEDAAADBDEDBDCCCDBDFFFDED"

    Returns: 25

  75. "ABABABABABABABABABABABABA"

    Returns: 17

  76. "HG DYIQMKQMKQNCHG NTXCLNTHG XQHG "

    Returns: 27

  77. "ASD"

    Returns: 2

  78. "BYGZIGSLBHLUDSLIGBYSLIGSLXVOAOAXVQUQUG"

    Returns: 34

  79. "QQQ"

    Returns: 2

  80. "XYZ"

    Returns: 2

  81. "AAABBAAAA"

    Returns: 6

  82. "AHAHAHAHAHKHAHAHAHAHA"

    Returns: 15

  83. "UVFGTTUQQPS UVFQES S UVNKGNQQPD"

    Returns: 27

  84. "AAAA"

    Returns: 3

  85. "AAABBB"

    Returns: 4

  86. "ABABABABABABABABA"

    Returns: 12

  87. "ABCDEF"

    Returns: 4

  88. "AAABBZAAAYABBUAAAWABB"

    Returns: 16

  89. "AABAABAABCCC"

    Returns: 8

  90. "ABCABCBCABCA"

    Returns: 8

  91. "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

    Returns: 34

  92. "XAABAABABAABA"

    Returns: 9

  93. "AHAHAHAHAHKHAHAHAHAHAKAHAHAHAHAHKHAHAHAHAHA"

    Returns: 31

  94. "AAABBABBAAAA"

    Returns: 8

  95. "BBBB"

    Returns: 3

  96. "ABABABABABABABABABABABABABABABABABABABABABABABABAB"

    Returns: 34

  97. "BBB"

    Returns: 2

  98. "IMPQZAGRIMPXIMP ZAGSZAIMPG"

    Returns: 20

  99. "ABAAAAAABACAAABABABAAA"

    Returns: 16

  100. "AAAQAAAWAAAEABAAABAYABAAABAUAAABAAAOAAABAAAPABAD"

    Returns: 36

  101. "ABABABABABABABABAB"

    Returns: 12

  102. "AABAABAABBAABAA"

    Returns: 10

  103. "ABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCAB"

    Returns: 34

  104. "AHAHAHAHAHKHAHAHAHAHAKAHAHAHAHAHKHAHAHAHAHA"

    Returns: 31

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: