Statistics

Problem Statement for "Repeat"

Problem Statement

We have come up with a compression technique for lowercase text that contains a lot of repetition. We will use 'R' to mean repeat the preceding text. The area to be repeated will be all the text since the closest preceding 'M' (or since the beginning of the text if there is no preceding 'M').

For example, "abcabcdabcabcdxyxyz" could be expressed in compressed form as "abcRdRMxyRz". To decompress this, the beginning abc is first repeated to become "abcabc", then "d" is added, and then all of that is repeated to make "abcabcdabcabcd". This is followed by the "xy" which is repeated and followed by the "z".

Create a class Repeat that contains a method minLength that is given the text to be compressed and that returns the minimum number of characters that can be used to express it with this compression technique. Of course all the 'R' and 'M' characters must be counted.

Definition

Class:
Repeat
Method:
minLength
Parameters:
String
Returns:
int
Method signature:
int minLength(String text)
(be sure your method is public)

Constraints

  • text will contain between 1 and 50 characters, inclusive.
  • Each character in text will be a lowercase letter 'a'-'z'.

Examples

  1. "aaaaaaaa"

    Returns: 4

    Either "aRRR" or "aaRR" is a way of compressing this to 4 characters.

  2. "aaaaaaa"

    Returns: 5

    One way is with "aaaRa"

  3. "bcdcdcdcdxcdcdcdcd"

    Returns: 12

    One way is "bMcdRRxMcdRR"

  4. "xyz"

    Returns: 3

    You can always use no 'R's or 'M's.

  5. "abxababababababab"

    Returns: 12

  6. "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"

    Returns: 8

  7. "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz"

    Returns: 9

  8. "aabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyy"

    Returns: 50

  9. "ttttttttttttttttttttttttttttttttttttttttttttttt"

    Returns: 10

  10. "ababaabbaaabbbababaabbaabbaabbbaabbbabab"

    Returns: 34

  11. "abcabcdabcabcdxyxyz"

    Returns: 11

    From the description.

  12. "ababcabcdabcdeabcdefabcdefgabcdefgh"

    Returns: 26

  13. "baaaaaabaaaaaaa"

    Returns: 9

  14. "bbabaababbabaaba"

    Returns: 9

  15. "baaaaaabaabaaabaabb"

    Returns: 14

  16. "aabbbbbbbaaabbbbbbba"

    Returns: 11

  17. "abaaaaaaabbbbabbaababbabbbba"

    Returns: 25

  18. "bbababcabbbcbcccbababbabacacccbba"

    Returns: 32

  19. "abecaebbaeccaaebdbdcadabdabbaaab"

    Returns: 31

  20. "bdafdefadbbfacedefeeddfacfddeafad"

    Returns: 33

  21. "b"

    Returns: 1

  22. "deaffabfbafbaec"

    Returns: 14

  23. "aaaaaaa"

    Returns: 5

  24. "acbcabccabbbcbbcbbbcbabbcbcacaacabcbabbacacbaac"

    Returns: 44

  25. "babababaababbaaaabba"

    Returns: 16

  26. "baabbaabbaabbaa"

    Returns: 12

  27. "badabaddcbdcbdbcdcadbdabdacbc"

    Returns: 27

  28. "edafakcd"

    Returns: 8

  29. "fabjbggihcegbaeeijhbhhbkdfhbcfbgkfij"

    Returns: 36

  30. "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

    Returns: 9

  31. "ccccacbbadbaaeaeabadaebdbbdcedadaacbecaaeceb"

    Returns: 43

  32. "gbvvsmvrmjqpkdow"

    Returns: 16

  33. "dccbaadh"

    Returns: 8

  34. "ffhblbidbjcidfljcaieejecba"

    Returns: 26

  35. "clbiidchckclfkllghlajhed"

    Returns: 24

  36. "lopdglrpmtifrmsoqooigjnkpmdqdtpthkqnlrfcgqbobiqd"

    Returns: 48

  37. "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxmxxxxxxxxxxxxxxxxxx"

    Returns: 17

  38. "abaaabaa"

    Returns: 5

  39. "babbabbabbabb"

    Returns: 6

  40. "qqqq"

    Returns: 3

  41. "abcdefghijklmnopqrstuvwxyz"

    Returns: 26

  42. "bcdcdcdcdxcdcdcdcd"

    Returns: 12

  43. "bcdcdcdcdcdcdcdcdbcdcdcdcdcdcdcdcd"

    Returns: 14

  44. "aaaabaaaabaaaabaaaabaaaabaaaabaaaabaaaac"

    Returns: 21

  45. "mxcdcdcdcdxcdcdcdcdbxcdcdcdcdxcdcdcdcdb"

    Returns: 14

  46. "dqefgqefghijmhijmqefgqefghijmhijmopopopopopopo"

    Returns: 24

  47. "abbbbbbbbabbbbbbbb"

    Returns: 10

  48. "aabcabcaabcabc"

    Returns: 8

  49. "aaaaaaaaccccccccaaaaaaaacccccccc"

    Returns: 13

  50. "accccccbaccccccb"

    Returns: 9

  51. "aabcdcdcdcdxcdcdcdcdabcdcdcdcdxcdcdcdcd"

    Returns: 22

  52. "kabcdabcdkkabcdabcdk"

    Returns: 11

  53. "asdvasdfasdasdfasdfasdasdffsdafasdfasdasdffasdfaas"

    Returns: 39

  54. "ababbababbbababbababb"

    Returns: 12

  55. "ababababababababababababababababababababababababab"

    Returns: 10

  56. "aaababababababaababbaabaabbbbbbbbbaaaaaaxaaaaaa"

    Returns: 36

  57. "aaaaaaaaaabbbbbbbbbbaaaaaaaaaabbbbbbbbbb"

    Returns: 16

  58. "abcabcabcabcabcabc"

    Returns: 8

  59. "bcdcdcdcdbcdcdcdcd"

    Returns: 10

  60. "xmnabcabcmnabcabc"

    Returns: 11

  61. "aaaaaaaaaaaabbbbbbbbbbbbaaaaaaaaaaaabbbbbbbbbbbb"

    Returns: 18

  62. "cababababcabababab"

    Returns: 10

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: