Statistics

Problem Statement for "Cyclemin"

Problem Statement

A rotation of a string S is the operation of moving its first character to the end. For example, if we rotate the string "abcde" we get the string "bcdea".

A cyclic shift of a string S is any string that can be obtained from S by a sequence of zero or more rotations. For example, the strings "abcde", "cdeab", and "eabcd" are some of the cyclic shifts of the string "abcde".

Given two equally long strings, the smaller one is the one with a smaller character at the first index where they differ. For example, "cable" < "cards" because 'b' < 'r'.

You are given a String s of lowercase letters and an int k. You are allowed to change at most k letters of s into some other lowercase letters.

Your goal is to create a string that will have the smallest possible cyclic shift. Compute and return that cyclic shift.

Definition

Class:
Cyclemin
Method:
bestmod
Parameters:
String, int
Returns:
String
Method signature:
String bestmod(String s, int k)
(be sure your method is public)

Constraints

  • s will contain between 1 and 50 characters, inclusive.
  • Each character in s will be between 'a' and 'z', inclusive.
  • k will be between 0 and the length of s, inclusive.

Examples

  1. "aba"

    1

    Returns: "aaa"

    We are allowed to change at most 1 character. Clearly, the optimal change is to change the 'b' into an 'a'.

  2. "aba"

    0

    Returns: "aab"

    We are not allowed to change anything. In this case, the answer is the smallest cyclic shift of the given string s.

  3. "bbb"

    2

    Returns: "aab"

  4. "sgsgaw"

    1

    Returns: "aasgsg"

    The optimal solution is to change the 'w' into an 'a', and then to take the cyclic shift that starts with the last two letters of s.

  5. "abacaba"

    1

    Returns: "aaaabac"

  6. "isgbiao"

    2

    Returns: "aaaisgb"

  7. "bzjpvdrsmfeirvconzumjpmtuikrelshsygfbcyyfq"

    21

    Returns: "aaaaaaaaaaaaaaaaaaaaabcyyfqbzjpvdrsmfeirvc"

  8. "pyoirqjghmvxfynqmszdbzgrnnjkjowg"

    3

    Returns: "aaabzgrnnjkjowgpyoirqjghmvxfynqm"

  9. "g"

    0

    Returns: "g"

  10. "vdrzwythetbdeyiloklbuyzupaltnebtwhyixs"

    4

    Returns: "aaaaabtwhyixsvdrzwythetbdeyiloklbuyzup"

  11. "romaxenbuuhxwisbbemcgdiosiuwctbkrvtpfnzrt"

    6

    Returns: "aaaaaaabuuhxwisbbemcgdiosiuwctbkrvtpfnzrt"

  12. "ikcwogejvhjiuxmbrkpzlzoxtgradpkxjntyo"

    2

    Returns: "aaadpkxjntyoikcwogejvhjiuxmbrkpzlzoxt"

  13. "dadtymegbsxpalzvjlsbuzbudrtkpdallvctpiqdbfydynvpdg"

    1

    Returns: "aadtymegbsxpalzvjlsbuzbudrtkpdallvctpiqdbfydynvpdg"

  14. "vzocfajqdapa"

    2

    Returns: "aaaavzocfajq"

  15. "naltgmahblriiwmxnwrfqignkxuoamsbyfrkwcgbfakktgybrg"

    35

    Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaablriiwmxnwr"

  16. "etyoxlivhoqp"

    0

    Returns: "etyoxlivhoqp"

  17. "ulsahabaxhdrqzaqozakekmvxaaoalppuraigpaykwovwuu"

    4

    Returns: "aaaaaaadrqzaqozakekmvxaaoalppuraigpaykwovwuuuls"

  18. "avaidvcadaqextkzojwfwzgymllezyiutmgawqsowxhfaantm"

    1

    Returns: "aaaidvcadaqextkzojwfwzgymllezyiutmgawqsowxhfaantm"

  19. "miqgbambkedajeeyskbtbmetaapizdhejwahalyxnakakqnjap"

    5

    Returns: "aaaaaaaakakqnjapmiqgbambkedajeeyskbtbmetaapizdhejw"

  20. "ailazqrfaydhoaqokblwsvbfyamrsfwarcnpmnpadzvyhta"

    2

    Returns: "aaaaazqrfaydhoaqokblwsvbfyamrsfwarcnpmnpadzvyht"

  21. "gkhtdvarapjfdfyrywjxsbjaagbzyqbs"

    8

    Returns: "aaaaaaaaaabsgkhtdvarapjfdfyrywjx"

  22. "rzjvlnbmypoobwqkgimzgbbamemarlafyvahddcwzztapqar"

    0

    Returns: "afyvahddcwzztapqarrzjvlnbmypoobwqkgimzgbbamemarl"

  23. "zaaymthcazlivzdlxxdguthapnsaaakfuvabsizwxcyicmhb"

    12

    Returns: "aaaaaaaaaaaaaaaaabsizwxcyicmhbzaaymthcazlivzdlxx"

  24. "dtwecxaajjotaaeazfhsakxcdvahyyvdljnejajsaereqhb"

    3

    Returns: "aaaaaafhsakxcdvahyyvdljnejajsaereqhbdtwecxaajjo"

  25. "ipqmjgejrlnidujxlaxzapaayzraqueunbotmkxfgsaewyv"

    41

    Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

  26. "etkzgajeizmmqjadfawqamynqaa"

    1

    Returns: "aaaetkzgajeizmmqjadfawqamyn"

  27. "javrejbaheektatpgyymwsrrntqidccgu"

    5

    Returns: "aaaaaaaheektatpgyymwsrrntqidccguj"

  28. "eemvbbjpiwxlhgwc"

    3

    Returns: "aaabbjpiwxlhgwce"

  29. "prgpeyahghwhaxtckzxtexcbazoamybhzaqfnhqgivhtaya"

    3

    Returns: "aaaaagpeyahghwhaxtckzxtexcbazoamybhzaqfnhqgivht"

  30. "afkusakhxazmvaoathnmadhwtnaahxaanophkmsaxeavwhh"

    3

    Returns: "aaaaaaanophkmsaxeavwhhafkusakhxazmvaoathnmadhwt"

  31. "taacathfkmqvggwahagblgxaaqjqzxlbarotabaagtwa"

    32

    Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

  32. "aaqkvafgmdjnevaaodu"

    0

    Returns: "aaoduaaqkvafgmdjnev"

  33. "cyfoavajgfalwofqqaaauwyxauopaafaxwcwwlraaqtfjxao"

    46

    Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

  34. "aazgygngapoxazazatkhabuifjmaaeanhlaigizaccqxpqtoea"

    2

    Returns: "aaaaagygngapoxazazatkhabuifjmaaeanhlaigizaccqxpqto"

  35. "ypaacaezrakzaaanroaancaipaoaromsapodayaacmsgna"

    32

    Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

  36. "raqurjsbeitejamojdfaqaxlaszeixvo"

    0

    Returns: "amojdfaqaxlaszeixvoraqurjsbeitej"

  37. "feafazgutoyh"

    0

    Returns: "afazgutoyhfe"

  38. "aftaobamcdaeaayljdvxroaayzpueaapgpaeqawkqngteqica"

    2

    Returns: "aaaaaljdvxroaayzpueaapgpaeqawkqngteqicaaftaobamcd"

  39. "jkmqakjjahwzaoaataexllptmoogaljgcakysjemt"

    35

    Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

  40. "xhbzzahmlrfeaasygaadfzhpkxtbaenvvmkjqmha"

    0

    Returns: "aadfzhpkxtbaenvvmkjqmhaxhbzzahmlrfeaasyg"

  41. "iepjaleavakbkalqwliaanyaspwaaajauvbxgxjabcimpwadz"

    31

    Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabcimp"

  42. "avrikkatdarp"

    0

    Returns: "arpavrikkatd"

  43. "qaibtfdzajonakybagasaka"

    6

    Returns: "aaaaaaaaaaabtfdzajonaky"

  44. "asmaaacuaatdbaakhaappvaoydaahaaajfslveoraamaacvaa"

    4

    Returns: "aaaaaaaaaaaacuaatdbaakhaappvaoydaahaaajfslveoraam"

  45. "jq"

    0

    Returns: "jq"

  46. "dtrbaauaaacsuigjkaawfpaarhapxlgknashdrauaacpairai"

    0

    Returns: "aaacsuigjkaawfpaarhapxlgknashdrauaacpairaidtrbaau"

  47. "aacaaaaasftbaaactplkmfoagazntaraargubsaaraekhars"

    44

    Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

  48. "lndpaxamgwqavdmahoaaadaaraeghflfaferaravalanafnaj"

    0

    Returns: "aaadaaraeghflfaferaravalanafnajlndpaxamgwqavdmaho"

  49. "salttcanncssaaaleauauaspaagaaapanwataalaaadsabacl"

    5

    Returns: "aaaaaaaaaaaaaaadsabaclsalttcanncssaaaleauauaspaag"

  50. "aaaaagtaebwdhaaakpwadapyviazahfcoaarva"

    3

    Returns: "aaaaaaaaaaagtaebwdhaaakpwadapyviazahfc"

  51. "faufnaayyayxaaaqdaagyqgeqabua"

    25

    Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

  52. "liaaawaaajwaaakagkcatdazlaidamqa"

    4

    Returns: "aaaaaaaaaaaaaagkcatdazlaidamqali"

  53. "aaaaaaraaarabaaaawautaagxqdawbaabaaaetnaraabaataa"

    3

    Returns: "aaaaaaaaaaaaaaaaaaawautaagxqdawbaabaaaetnaraabaat"

  54. "aaysaymwafamahacaraanaazacaaatanaaaaazkp"

    3

    Returns: "aaaaaaaaaaaaazkpaaysaymwafamahacaraanaaz"

  55. "acastdunzdtwtpatmsqqzzauajaaoaoaaaataiaoaaaahayax"

    6

    Returns: "aaaaaaaaaaaaaaaaaaaahayaxacastdunzdtwtpatmsqqzzau"

  56. "gaaaazaadaa"

    0

    Returns: "aaaazaadaag"

  57. "tfajbaawnaamevdxcaxaaaaaapacaoajexavacarahafkwar"

    5

    Returns: "aaaaaaaaaaaaaaaexavacarahafkwartfajbaawnaamevdxc"

  58. "aaotggeapqaaaxafazoajfaaajtajaaazajsanaaa"

    0

    Returns: "aaaaaotggeapqaaaxafazoajfaaajtajaaazajsan"

  59. "kjmaazazfaoylaxaaaaaagazyxsagaaaasaaegaaaqaaazmx"

    7

    Returns: "aaaaaaaaaaaaaaaaaaaaaegaaaqaaazmxkjmaazazfaoylax"

  60. "aaakayuaaazul"

    0

    Returns: "aaakayuaaazul"

  61. "ahaaaaarkaaaaaamaaaravahaizgqawasaaa"

    29

    Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

  62. "aaafxcapvaaagaamaaadtaaxbaasaaaaaamxadaaarfaaoq"

    0

    Returns: "aaaaaamxadaaarfaaoqaaafxcapvaaagaamaaadtaaxbaas"

  63. "cjoakajpaxaadraagzaaaaaartcaaaaaadazhaaacaaarrkaa"

    4

    Returns: "aaaaaaaaaaaaaaaaarrkaacjoakajpaxaadraagzaaaaaartc"

  64. "dbaawaaaaaazaaa"

    0

    Returns: "aaaaaazaaadbaaw"

  65. "yaalsavaaaalfaahaqarabaaawoavovaqjips"

    9

    Returns: "aaaaaaaaaaaaaaaaaaaaaaaawoavovaqjipsy"

  66. "aacaoaasaaraax"

    0

    Returns: "aacaoaasaaraax"

  67. "naagwasu"

    2

    Returns: "aaaaasun"

  68. "aaajaqafaaoaxkaj"

    4

    Returns: "aaaaaaaaaaaaoaxk"

  69. "vaanaarsaahjaaaacaakaaapaoafasaaaafaaaaaaaofcaah"

    0

    Returns: "aaaaaaaofcaahvaanaarsaahjaaaacaakaaapaoafasaaaaf"

  70. "aoxaahaaqaoaaaa"

    2

    Returns: "aaaaaaaaaaoxaah"

  71. "auuxapaaagajaaaaahaynamaoaayyvnaaariaoarpgwbav"

    14

    Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaoarpgwbavauux"

  72. "gdhxalaaamydaamuaqymaxaaaaaaivaaylas"

    0

    Returns: "aaaaaaivaaylasgdhxalaaamydaamuaqymax"

  73. "qhesaarancaqaaaaaaaaaaaafaaaaauaaaahx"

    35

    Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

  74. "aaoraapav"

    4

    Returns: "aaaaaaaaa"

  75. "aahaaa"

    3

    Returns: "aaaaaa"

  76. "aasaaavaakaj"

    2

    Returns: "aaaaaaaaakaj"

  77. "lauanuqaeakakauaaaaaaaaaztraaxizajxhaaagaaaaaaaa"

    30

    Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

  78. "iaaanjaaaabaaa"

    1

    Returns: "aaaaaaaaiaaanj"

  79. "aaarajaaaaaaaaaaaaaauzupuaaaaaaaaraaapaaaacaaaaa"

    7

    Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaupu"

  80. "aaaaaaaaaxacdraaaaaaaaaxaaaayazcaacaoaataaanaane"

    4

    Returns: "aaaaaaaaaaaaaaaaaaaaaaaxaaaayazcaacaoaataaanaane"

  81. "aaaaacaaaaaaaaaafaaaaaxaxamaaaaaaaaazaaavroaaeaa"

    47

    Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

  82. "aaaawaaaaafasaamaauaaaawqa"

    4

    Returns: "aaaaaaaaaaaaaaaaaaaafasaam"

  83. "rqaaatgaaaiaaaaiaooaaaaaaaaaaaaamaaaaaaaraaaaaat"

    4

    Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaatrqaaatgaaaiaaaai"

  84. "aaaaaaaaaaamaaaaaasaayanugaaa"

    1

    Returns: "aaaaaaaaaaaaaaaaaaaaasaayanug"

  85. "akamaaaaaaasaaaaaaaaaanaaaaaavaaaaaaapaaaaaavas"

    28

    Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

  86. "aazaaaaadamaaaaeaaaaacaaaawata"

    4

    Returns: "aaaaaaaaaaaaaaaaaaaaaaawataaaz"

  87. "aayhaaaaqaasbaaaaaaayahaajuabaaavaaaraaaaaaaala"

    4

    Returns: "aaaaaaaaaaaaaaaaaaaaaaqaasbaaaaaaayahaajuabaaav"

  88. "aavaaalaaaaaaaaaaaaaaaaaiayaaaaboaaa"

    3

    Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaayaaaabo"

  89. "avasdaaaaaaaaaaaaaaaaaaaazaanaaaiaaaaaaa"

    30

    Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

  90. "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

    2

    Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

  91. "auaaaakaajaaaaaaaaaaaaabaaaaqaaagaaaiaaadajalaaaa"

    7

    Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaadajal"

  92. "aaaavataalaaaaaaaaaaaearaaaadaaaaaaaaoacaaaraaaa"

    3

    Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaoacaaaraaaaaaaavataal"

  93. "aaaaaxaqaaaagaaaaataatyaaaaaaaaaaaaaaayaapaaaaaa"

    7

    Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaag"

  94. "raaaaaaaaaaaaaamaaaaaaaaaraaaaaaaaaaaaafalaaaaaa"

    1

    Returns: "aaaaaaaaaaaaaaaaaaaaaaaaraaaaaaaaaaaaafalaaaaaar"

  95. "aaaaahaaaaaaaabaaaaabaaaaaaaaazaaaaaaaaaaaaaaa"

    0

    Returns: "aaaaaaaaaaaaaaaaaaaahaaaaaaaabaaaaabaaaaaaaaaz"

  96. "aaaaaaaaaaaaaaaaaaaazaaaaaaaaaaaaaaaaaaaaaaaaaa"

    1

    Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

  97. "aaaaa"

    4

    Returns: "aaaaa"

  98. "aaaaaaaaaaaaajaaaawcaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

    2

    Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac"

  99. "aacaaaaaaaaaaaaaaataaaaaaagaaawakaaaaaaaaaaaaau"

    1

    Returns: "aaaaaaaaaaaaaaaaaaaaaaagaaawakaaaaaaaaaaaaauaac"

  100. "aa"

    0

    Returns: "aa"

  101. "aaaanaaaaaaaacaaaaaaaadaasaaaaaaaaaaaaaaaaaaaaaama"

    17

    Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

  102. "aaaaaaaaaa"

    4

    Returns: "aaaaaaaaaa"

  103. "aoaaaaaaaaafaaaaaaaa"

    6

    Returns: "aaaaaaaaaaaaaaaaaaaa"

  104. "aaaaaaaaaaaaaaaafaaaaaaaaaaaaaaalaaabaaaaaaaaaaa"

    1

    Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaalaaab"

  105. "aaaaaaaaaaaaaaaaaaaaaaa"

    6

    Returns: "aaaaaaaaaaaaaaaaaaaaaaa"

  106. "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

    0

    Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

  107. "abbzzzzc"

    4

    Returns: "aaaaabbz"

  108. "paai"

    1

    Returns: "aaai"

  109. "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz"

    25

    Returns: "aaaaaaaaaaaaaaaaaaaaaaaaazzzzzzzzzzzzzzzzzzzzzzzzz"

  110. "bbcbc"

    1

    Returns: "abbcb"

  111. "fdasfsadfdsfsfdsfsdfsdfsdddsfsdfsd"

    11

    Returns: "aaaaaaaaaaaaadfdsfsfdsfsdfsdfsddds"

  112. "s"

    1

    Returns: "a"

  113. "aab"

    2

    Returns: "aaa"

  114. "bac"

    0

    Returns: "acb"

  115. "aacaabbaa"

    1

    Returns: "aaaaaaabb"

  116. "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz"

    0

    Returns: "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz"

  117. "bavddeegfdsegaaaccvv"

    0

    Returns: "aaaccvvbavddeegfdseg"

  118. "aabbaba"

    1

    Returns: "aaaaabb"

  119. "z"

    0

    Returns: "z"

  120. "b"

    1

    Returns: "a"

  121. "a"

    1

    Returns: "a"

  122. "bac"

    1

    Returns: "aab"

  123. "zzbb"

    2

    Returns: "aabb"

  124. "azazazzzzzzzzzza"

    5

    Returns: "aaaaaaaaazzzzzzz"

  125. "zzaxazzzzzzz"

    1

    Returns: "aaazzzzzzzzz"

  126. "adcb"

    1

    Returns: "aacb"

  127. "zazbc"

    2

    Returns: "aaabc"

  128. "bwbbcc"

    1

    Returns: "abbccb"

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: