Statistics

Problem Statement for "MagicNaming"

Problem Statement

Today is the Christmas Eve. People around the world celebrate this holiday. The following story takes place in the land of reindeer, where Santa Claus resides.


The reindeer have invented a new magic spell. To pick a name for the spell, they decided to concatenate their own names.


Of course, this can be done in multiple ways. For example, if there are two reindeer called "bob" and "bobby", they could call the spell either "bobbobby" or "bobbybob". To resolve this ambiguity, the reindeer picked the lexicographically smallest possibility. (In this case, that would be "bobbobby".)


You are given a String magicName. This is the name of the spell. You do not know how many reindeer invented the spell and what their names were. Your method must compute and return the largest possible number of reindeer that could have invented the spell.

Definition

Class:
MagicNaming
Method:
maxReindeers
Parameters:
String
Returns:
int
Method signature:
int maxReindeers(String magicName)
(be sure your method is public)

Notes

  • Given two distinct strings of equal length, the lexicographically smaller one is the one with a smaller character in the first position where they differ
  • The name of each reindeer is a nonempty string of lowercase letters.
  • It is always possible that the spell was created by a single reindeer, so the return value is always defined.
  • Note that multiple reindeer may share the same name. See Example #5 for clarification.

Constraints

  • The length of magicName will be between 1 and 50, inclusive.
  • Each character in magicName will be between 'a' and 'z', inclusive.

Examples

  1. "aba"

    Returns: 2

    The magic spell called "aba" could have been invented by two reindeer called "a" and "ba". Note that this spell could not have been invented by three reindeer. Their names would have to be "a", "b", and "a". However, reindeer with these names would choose the name "aab" for their spell.

  2. "babbaba"

    Returns: 2

    In this case there might have been two reindeer called "ba" and "bbaba". More than two reindeer would never pick this name for their spell.

  3. "philosophersstone"

    Returns: 5

  4. "knuthmorrispratt"

    Returns: 7

  5. "acrushpetrtourist"

    Returns: 7

  6. "makotoivan"

    Returns: 4

  7. "abcdefghijklmnopqrstuvwxyz"

    Returns: 26

  8. "x"

    Returns: 1

  9. "bba"

    Returns: 1

  10. "bbababaabaabaa"

    Returns: 1

  11. "abaababaaababaabba"

    Returns: 5

  12. "bbbaaaabbaabaabbbabaaaaaaabb"

    Returns: 4

  13. "ba"

    Returns: 1

  14. "babaaaba"

    Returns: 2

  15. "bbabbabaababbbababbbbaaaaaaabbabbbbaabbbbbbaaaa"

    Returns: 5

  16. "bbbaababbbbbbaababaabaaab"

    Returns: 3

  17. "abbaaaa"

    Returns: 2

  18. "bbaaababaaaabbbbbaabbbaa"

    Returns: 3

  19. "ababbbbaabaaaaabaabababaabbaaabaa"

    Returns: 6

  20. "abbababbabbbaa"

    Returns: 5

  21. "bababaa"

    Returns: 1

  22. "aaaaabbaaaabbaabab"

    Returns: 9

  23. "baabababbaaaabbaaaaaababaabbbabbaba"

    Returns: 5

  24. "aababbbbbaabbabaaaabbbbaababababbabbaaabbababbbbba"

    Returns: 11

  25. "aaabaaaaaa"

    Returns: 4

  26. "baabbaaabbbababba"

    Returns: 4

  27. "babaaaabbbabbabbaabaabbabaa"

    Returns: 4

  28. "baaaaaaaabbabbaaa"

    Returns: 3

  29. "aabbbababbabbbbaaaabaaaabaabaaaabbba"

    Returns: 8

  30. "abaababaabaabababbabaab"

    Returns: 8

  31. "abbabababbbaaaabbaaaabaaabbbabbabbaa"

    Returns: 6

  32. "aabbababbabbaababbaabbbababababbbaabaab"

    Returns: 11

  33. "baabbbbaaabaabaaabababbbaaabaabab"

    Returns: 5

  34. "aaababaaabaaaaaaababbbaababaabbbbbaabba"

    Returns: 9

  35. "bababb"

    Returns: 4

  36. "abbaabaabbbbabaaaabbabbaaabaaabbbbababba"

    Returns: 8

  37. "abaaaabbababaaababaaabbbaabbabbaabbbbbaabbaaabba"

    Returns: 8

  38. "aaabbaabbbbaabaaabbbaabbababbabbabaa"

    Returns: 9

  39. "aabbbbbbabbbbabbaaaabbbbbaaabaaaabaaab"

    Returns: 6

  40. "kgkjjihjkggjhkjijggh"

    Returns: 2

  41. "jhkjhjhgkghjhijjgggiijgkkjgghghikikigihkhkikhghkk"

    Returns: 6

  42. "ijhhkgihjigjhhkikghhkh"

    Returns: 5

  43. "hijjggggjhhgiihjkkijgii"

    Returns: 6

  44. "kjjkkgkkjhiihhhkkggjkhjjkijjhkhkghgigjjhijkhi"

    Returns: 3

  45. "jjikjgjgihkijigihjj"

    Returns: 3

  46. "ghhgkkjjighhhghhgh"

    Returns: 5

  47. "kkkjkiiikkijkihihigkkikhkgikjghgjjgkjjij"

    Returns: 1

  48. "ghkgkkgjihkjkggjgkkkikiijgjkjhikghgjihihhhghiig"

    Returns: 8

  49. "jihhgkjjhkkjiikjgg"

    Returns: 3

  50. "kj"

    Returns: 1

  51. "gjikjkikikjg"

    Returns: 6

  52. "ig"

    Returns: 1

  53. "jjjjkkjjghjgkkihjhijkjjgkhhgkjhkikghijjjkkgkgggkg"

    Returns: 7

  54. "kijjiihhgjkihghhgkjkjjkjhi"

    Returns: 2

  55. "khjghiijjgkgjkhigjgjggjijikjkiijki"

    Returns: 3

  56. "ihhhhgkghikkkkgjggj"

    Returns: 4

  57. "jjjgkigjggiihhggghiijkhikjkjghhii"

    Returns: 4

  58. "hhjgghgkigjkkiiijjjkikjjjghihhgjgjkijjhij"

    Returns: 11

  59. "ikhjjkjg"

    Returns: 4

  60. "kjhhikkggjkhkjkkhikhgghijiiigkiigjgijijkgjkgjh"

    Returns: 3

  61. "hgghijikghgjkjhkigggkjikghjghgkhghgijhjjki"

    Returns: 10

  62. "khggjgikigjkkjihkkkkhijkhiigigkjjik"

    Returns: 5

  63. "kigkjggiigkikjjghh"

    Returns: 3

  64. "jkghjjkhkkjkijkgihgjihgighhgggkghkihgggiikjkkihg"

    Returns: 7

  65. "iigigkihkhgjhjijkghhkjgjkjjigih"

    Returns: 7

  66. "jjhggggghhjihikkjj"

    Returns: 3

  67. "iihjhkjj"

    Returns: 4

  68. "iikijhihkiggggiihhkggkhghkhhikii"

    Returns: 7

  69. "kih"

    Returns: 1

  70. "fy"

    Returns: 2

  71. "zikjbkltvnakagmanazsyvsfxbgnvifkjghtczabqxkpf"

    Returns: 2

  72. "mrpewjulnovfikpggkhvpbjhnnuiefiubxpjtplupvixi"

    Returns: 9

  73. "ctoskkhzmjpvd"

    Returns: 5

  74. "hdvnaznbqwzljo"

    Returns: 6

  75. "lbjoqfnsozahrlpjjhxakkhofvwwsksmtyfobojrdc"

    Returns: 8

  76. "oykvlbosegruxmbj"

    Returns: 4

  77. "ofrbedconibeupaibqbhrsbfsyiiizbuzyswdcis"

    Returns: 10

  78. "tencergxvyaajtmssvnsighuvfdssnxmkscegxyvqeeixvnxze"

    Returns: 8

  79. "wtgtvejlbkxnzmxcbufwlikrpzt"

    Returns: 4

  80. "jssgaihkpjcplkkixvilr"

    Returns: 5

  81. "hbmfrmk"

    Returns: 3

  82. "esgqtvblarjegjcfvvl"

    Returns: 6

  83. "ldbgqrkal"

    Returns: 3

  84. "wvurzhgvpnnrlbzbbsijdgdxpjueticwbqnvnlrpkz"

    Returns: 3

  85. "tuylyhmajmdmbmgfgqxbgumjtcbqs"

    Returns: 3

  86. "fblwddghhsevzhuosjeusfafrwxaofk"

    Returns: 10

  87. "sqxmiybmdtvnfgysmanlealrs"

    Returns: 4

  88. "zshqbonnrmhuclfuzzi"

    Returns: 2

  89. "npsovhphzcghggzxkhmuzteo"

    Returns: 6

  90. "jefrytnowmrcvl"

    Returns: 5

  91. "kfdfalqejdkczoeyqifrmhrcrgrccvbjm"

    Returns: 7

  92. "scilsb"

    Returns: 1

  93. "nrlrgsewnysafebzhkrqmyobbdtkqgaakys"

    Returns: 6

  94. "oqgcmafzreciidbkalrcufuudtyhzwpjxnysz"

    Returns: 9

  95. "ufbmsartfadrobobrnvfdprtpunmwydygfi"

    Returns: 5

  96. "bcptxzukqamlqjqnnpesotnb"

    Returns: 9

  97. "axcbbhdhsuztecchhjyjfssydfajpnvxsxda"

    Returns: 12

  98. "bhwkoimhvomdmhlb"

    Returns: 5

  99. "qgzglsqxyntjkvofwegjzfsdpiucajpgkaeyqcsqteu"

    Returns: 6

  100. "rlksygnlmjyghjlwlrvmfpopkijpdyxsttwipopbuzkdaposfe"

    Returns: 7

  101. "kfxitbtsppvzelpcqyafygwefhnbxlvbktrroldrcfwicllxze"

    Returns: 8

  102. "tlensfbnbutucfygzezfrtdfgepanmrjkooysfnohsujbqugkh"

    Returns: 6

  103. "dnmywfaaiwruzlilgbiaybtdiledgwbyynwaxixvtjbgsivmwt"

    Returns: 10

  104. "sehqcxgckhjbuihrkpqiffvpzslhrlmtzglpsemskthxlqiady"

    Returns: 6

  105. "rzsoombuvcwtxczydqpgznqqnhkubylzspvwbsopucfmpsfnqm"

    Returns: 9

  106. "vzsrpttzrpnvbmxsxlderudrzmtrkprjgopapmmxqhyctdeouf"

    Returns: 4

  107. "bvonublagnfwdutpabtybplbyjsfyphmktksknfaxqetkcphnz"

    Returns: 9

  108. "wxaiuhxwweqmfhbplitafbmrketgbuhxiziktduccmknvwzpnt"

    Returns: 5

  109. "goibuohakixubdzfmxjfvcmvztlgrrsptddpqgruujkptkjocn"

    Returns: 10

  110. "oqkgwjeejkryphryhjpmperhvinwjtyjtajcbsdpyfjdkhntfc"

    Returns: 7

  111. "xbzmdhaabycsdklmampemxbwhtxbkkexqylacaeakuuhhqsbhm"

    Returns: 3

  112. "miuwrtwqulwvsmbeyrtvtkdyodpbttlvmlizgjrsbqtbqerctk"

    Returns: 8

  113. "uxjzyqnfocqulsyzkmdnnivghsamxlatwcnjpmjvsnuvutehje"

    Returns: 5

  114. "gqsstjukyaxhrjdieddbocfzmhjtvnejkgqtfajwpoepdsoatv"

    Returns: 10

  115. "wiagbotxzkxtnybgpqfgcasuhpjyzhjastspsfbulwqslzpjgm"

    Returns: 6

  116. "hhjkmyshucbsjcwrgjtuiqtfzesttiozihknniwibhyrdjxpqq"

    Returns: 11

  117. "pjwkmvurnjtgoggscxgxnfrvsynsjswowgerhspgeoldlohymq"

    Returns: 7

  118. "avypnpbejmosoymuatjzplygnjnyqelawbuhwbtzffxkvauadc"

    Returns: 12

  119. "eoliamiiowizghyrluqycfnuebfrkzvmuvzyyvtfwrtrstupxh"

    Returns: 13

  120. "zzzzz"

    Returns: 5

    Note that multiple reindeer may share the same name.

  121. "gmezsyfytjxyefasinzxyfdktwszdahqszixzbdeoadtrddasd"

    Returns: 9

  122. "rri"

    Returns: 1

  123. "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz"

    Returns: 49

  124. "gabzhijk"

    Returns: 5

  125. "abcdefghijabcdefghijabcdefghijabcdefghijabcdefghij"

    Returns: 14

  126. "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

    Returns: 50

  127. "ahahahdjflahahahdjflahahahdjflahahahdjflahahahdjfl"

    Returns: 13

  128. "abcdeabcdeabcdeabcdeabcdeabcdeabcdeabcde"

    Returns: 12

  129. "fdgsgfhasyufbdsjcvdshbuifsdhbfhsdbfhsfsfdsbvfhgsfh"

    Returns: 8

  130. "rubenjosesue"

    Returns: 4

  131. "qowiuerjsadhjasgdbmncbvjsafgwiueryweirqpefasdj"

    Returns: 7

  132. "ardebaoncadencedipingeerrorfghijklmnopqrstuvwxyouz"

    Returns: 28

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: