Statistics

Problem Statement for "EllysSortingTrimmer"

Problem Statement

Elly has a String S of uppercase letters and a magic device that can modify the string. The strength of the device is an int L.

The device is used in the following way. The user enters a 0-based index i such that 0 <= i <= length(S)-L. The device then performs the following changes:
  • It leaves the first i characters (i.e., characters with indices 0 through i-1) untouched.
  • It rearranges the next L characters (i.e., characters with indices i through i+L-1) into alphabetical order.
  • It erases all the remaining characters (i.e., characters with indices i+L and more). Note that for i=length(S)-L no characters are erased.
The girl can use this "sorting trimmer" as many times as she likes. After each use she is left with the new version of the string.

In the examples below we use brackets to highlight the region that shall be sorted. For example, "ABRA[CADAB]RA" means that L=5 and Elly chose i=4. The device keeps the letters in front of the brackets, sorts the letters in the brackets, and throws away the rest. Here is one way how Elly could have used a device with L = 5, starting with the string S = "ABRACADABRA":
  1. "ABRAC[ADABR]A" -> "ABRACAABDR"
  2. "ABR[ACAAB]DR" -> "ABRAAABC"
  3. "A[BRAAA]BC" -> "AAAABR"
You are given the String S and the int L. Return the lexicographically smallest string Elly can obtain.

Definition

Class:
EllysSortingTrimmer
Method:
getMin
Parameters:
String, int
Returns:
String
Method signature:
String getMin(String S, int L)
(be sure your method is public)

Notes

  • A string A is lexicographically smaller than string B if A contains a smaller character in the first position where they differ. In case one of the strings ends before they have a different character, the shorter one is considered smaller.

Constraints

  • S will contain between 2 and 50 characters, inclusive.
  • L will be between 2 and |S|, inclusive, where |S| denotes the number of characters in S.
  • S will consist of uppercase characters of the English alphabet, only ('A'-'Z').

Examples

  1. "ABRACADABRA"

    5

    Returns: "AAAAA"

    Please note that the example in the problem statement does not obtain the lexicographically smallest string. In fact, it is optimal to start by using the device on the last five characters of the string, transforming it from ABRACA[DABRA] to ABRACAAABDR.

  2. "ESPRIT"

    3

    Returns: "EIP"

    We can obtain the answer in the following steps: ES[PRI]T -> ESIPR E[SIP]R -> EIPS [EIP]S -> EIP

  3. "BAZINGA"

    7

    Returns: "AABGINZ"

    We can use the sorting trimmer on the entire word.

  4. "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

    13

    Returns: "ABCDEFGHIJKLM"

    Even though the string is already sorted, shorter strings are considered lexicographically smaller, so we can use the device once to make the string as short as possible.

  5. "GOODLUCKANDHAVEFUN"

    10

    Returns: "AACDDEFGHK"

  6. "AAAWDIUAOIWDESBEAIWODJAWDBPOAWDUISAWDOOPAWD"

    21

    Returns: "AAAAAAAAABBDDDDDDDEEI"

  7. "TOPCODER"

    3

    Returns: "CDT"

  8. "AAAAAAAAAAAAAAAAAACB"

    13

    Returns: "AAAAAAAAAAAAA"

  9. "WITHOUTITIMJUSTESPRIT"

    21

    Returns: "EHIIIIJMOPRSSTTTTTUUW"

  10. "RIGHTNOWYOUSHOULDBELAUGHING"

    5

    Returns: "ABDER"

  11. "GOGOKEFAKEFAISNOTBLUEYET"

    8

    Returns: "AABEEEEG"

  12. "ZZAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

    2

    Returns: "AZ"

  13. "ZZZZZZZZZZZZZZAAAAAAAAAAAAAAA"

    7

    Returns: "AAAAAAZ"

  14. "GOOGLE"

    3

    Returns: "EGG"

  15. "GGNORE"

    5

    Returns: "EGGNO"

  16. "AZAZAZAZAZAZAZAZAZAZAZAZAZAZAZAZAZAZAZAZAZAZAZAZAZ"

    25

    Returns: "AAAAAAAAAAAAAAAAAAAAAAAAA"

  17. "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

    13

    Returns: "ABCDEFGHIJKLM"

  18. "ZYXWVUTSRQPONMLKJIHGFEDCBA"

    13

    Returns: "ABCDEFGHIJKLZ"

  19. "TOPCODER"

    2

    Returns: "CT"

  20. "TOPCODER"

    3

    Returns: "CDT"

  21. "TOPCODER"

    5

    Returns: "CDEOT"

  22. "TOPCODER"

    6

    Returns: "CDEOOT"

  23. "TOPCODER"

    7

    Returns: "CDEOOPT"

  24. "TOPCODER"

    8

    Returns: "CDEOOPRT"

  25. "AAAAAABCDEFKYDETREZAZZYYYRRZ"

    5

    Returns: "AAAAA"

  26. "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAZYX"

    20

    Returns: "AAAAAAAAAAAAAAAAAAAA"

  27. "MOMSEEIAMWRITINGTESTSFORTOPCODERTCOROUNDONE"

    13

    Returns: "ACCDDEEEEEFGM"

  28. "CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDD"

    3

    Returns: "CCC"

  29. "ZZZYYYGGGGXXXCBAABCFFFFFFTRRAWD"

    2

    Returns: "AZ"

  30. "ZZZYYYGGGGXXXCBAABCFFFFFFTRRAWD"

    3

    Returns: "AAZ"

  31. "ZZZYYYGGGGXXXCBAABCFFFFFFTRRAWD"

    4

    Returns: "AAAZ"

  32. "ZZZYYYGGGGXXXCBAABCFFFFFFTRRAWD"

    5

    Returns: "AAABZ"

  33. "ZZZYYYGGGGXXXCBAABCFFFFFFTRRAWD"

    6

    Returns: "AAABBZ"

  34. "ZZZYYYGGGGXXXCBAABCFFFFFFTRRAWD"

    7

    Returns: "AAABBCZ"

  35. "ZZZYYYGGGGXXXCBAABCFFFFFFTRRAWD"

    8

    Returns: "AAABBCCZ"

  36. "ZZZYYYGGGGXXXCBAABCFFFFFFTRRAWD"

    9

    Returns: "AAABBCCDZ"

  37. "ZZZYYYGGGGXXXCBAABCFFFFFFTRRAWD"

    10

    Returns: "AAABBCCDFZ"

  38. "ZZZYYYGGGGXXXCBAABCFFFFFFTRRAWD"

    11

    Returns: "AAABBCCDFFZ"

  39. "ZZZYYYGGGGXXXCBAABCFFFFFFTRRAWD"

    12

    Returns: "AAABBCCDFFFZ"

  40. "ZZZYYYGGGGXXXCBAABCFFFFFFTRRAWD"

    13

    Returns: "AAABBCCDFFFFZ"

  41. "QZZYYYGGGGXXXCBAABCFFFFFFTRRAWD"

    7

    Returns: "AAABBCQ"

  42. "HAPJIABBNYDBWHYKZUPCUXMUSHNXWJC"

    30

    Returns: "AABBBCCDHHHIJJKMNNPPSUUUWWXXYY"

  43. "ZBMDDNXROMTVTPUGPDKBKTQDTGFUJCUTPFFMS"

    3

    Returns: "BBZ"

  44. "RDFTODEBLEEALCAPOV"

    16

    Returns: "AABCDDEEEFLLOOPR"

  45. "NQLWGMCYVDIKTSXRLBOYUWLNSPYVOPUUFKSXDPYOVINYGUYU"

    41

    Returns: "BCDDFGGIIKKLLLMNNNOOOPPPQRSSSTUUUUUVVVWWX"

  46. "VZBMHXVJBRTKBXYCBBJOKETEHEE"

    27

    Returns: "BBBBBCEEEEHHJJKKMORTTVVXXYZ"

  47. "SLIPRLZGUKFGGZGGZFYBZYUX"

    11

    Returns: "BFFGGGGGIKS"

  48. "NTIDXFZTRLDOMJQKVBPQHBSIUJWDAWZQSQEFRRZE"

    25

    Returns: "ABBDDDEEFFHIIJJKLMNOPQQQQ"

  49. "XNGZNKVDFPKEQJRRSJJCNAFDAJNEHGBWWZ"

    28

    Returns: "AABCDDEEFFGGHJJJJKKNNNNPQRRX"

  50. "TOSNCWPMPGBAKSHPLRCUH"

    14

    Returns: "ABCCGHHKLMNOPT"

  51. "VGLJFMYQXUUJOMPFJHREEPWJMOJKEX"

    27

    Returns: "EEEFFGHJJJJJKLMMMOOPPQRUUVW"

  52. "TMOXPKAYZENMLCTGMQNPKXNADCZDIAUWTBHGHTUHHLETIVAM"

    32

    Returns: "AAAABCCDDEEGGHHHHIIKKLLMMMMNNNOT"

  53. "RLOJRAPGVLNRAZKHRPUVTLVFFBKJISKZBEPWHPIGA"

    24

    Returns: "AAABBEFFGGHHIIJJKKKLLLNR"

  54. "PLMINCKDMFYQQRQIJHIPRUSEMPAJBZHQWJMUTPT"

    39

    Returns: "ABCDEFHHIIIJJJKLMMMMNPPPPQQQQRRSTTUUWYZ"

  55. "XZEIGOBEDYKBATQDNLBWQXOHKDXTIFMRRR"

    32

    Returns: "ABBBDDDEEFGHIIKKLMNOOQQRRRTTWXXX"

  56. "OPHCCLYCFBEIMQWPJEOFXLIORCZDFMOXPGGOQJVOBDFYM"

    45

    Returns: "BBCCCCDDEEFFFFGGHIIJJLLMMMOOOOOOPPPQQRVWXXYYZ"

  57. "PIKPWZSIXCELWZHWPPOIEYKWDYYIMXEMBXXROICIEFPRYZJJJU"

    50

    Returns: "BCCDEEEEFHIIIIIIJJJKKLMMOOPPPPPRRSUWWWWXXXXYYYYZZZ"

  58. "VKXMBOODNVBCHECYYZURLLYSPXNMKSDAAMVGNFDFFZHRQTGBRW"

    49

    Returns: "AABBBCCDDDEFFFGGHHKKLLMMMNNNOOPQRRRSSTUVVVWXXYYYZ"

  59. "FXGWGRFXKOMHZMSJVOFZGLOCJTRZSZXDOLZDUZKAAKPDBEIEFL"

    50

    Returns: "AABCDDDEEFFFFGGGHIJJKKKLLLMMOOOOPRRSSTUVWXXXZZZZZZ"

  60. "LVYOUQBWCWOAEKRSQIMCERSQBCTQKMIXDGXSPUYQLLRTZEAT"

    42

    Returns: "AABBCCCDEEEGIIKKLLLMMOOPQQQQQRRRSSSTTTUUVW"

  61. "VZZWFAHIPXPDIJMUAVVPVIDFITSTZBCRAYSXNIKASIUQBNXFJ"

    49

    Returns: "AAAABBCDDFFFHIIIIIIJJKMNNPPPQRSSSTTUUVVVVWXXXYZZZ"

  62. "DEIFIHROLLRMRLQBOPHHMKLIRHHPFQIOAZRCFTCPWAMGSS"

    44

    Returns: "AABCCDEFFFGHHHHHIIIIKLLLLMMMOOOPPPQQRRRRRSST"

  63. "CRLYNZVWCJIWELRDONGTTSRCHSXCWSDFCHCIHFMK"

    40

    Returns: "CCCCCCDDEFFGHHHIIJKLLMNNORRRSSSTTVWWWXYZ"

  64. "SBTHMGRJWYMODEWHJWFJEBWMJTYQQHEBHVVK"

    30

    Returns: "BBBDEEEFGHHHHJJJJKMMMOQQRSTTVV"

  65. "QZMBXCQJMYZCMJCTPISYGNRFGZCCCKSZXTJYZPFWQRRKFDXS"

    31

    Returns: "BCCCCCCDFFFGGIJJJKKMMMNPPQQQRRR"

  66. "GUXXCPBRMZJSVLKIGNBLNFKUYBMXKRIXGT"

    25

    Returns: "BBBCFGGGIIJKKKLLMMNNPRRST"

  67. "RSFKYTGDKTNAFKYAB"

    10

    Returns: "AABDFFGKKR"

  68. "WVILO"

    3

    Returns: "ILW"

  69. "GPXUCQGKQLXMDZAICPRGSGGTWLPWUIQBJQYHZENAWZRMGYLZDP"

    49

    Returns: "AABCCDDEGGGGGGHIIJKLLLMMNPPPPQQQQRRSTUUWWWXXYYZZZ"

  70. "CBRJIMJFPVXZJGIRMKHYTGAGHBYMUXXFAMNMWNOTC"

    25

    Returns: "AABBCCFFGGGHHIIJJJKMMMMMN"

  71. "BQLGPPUKRCWMBSQUIQZOPGAEQOITLTLUKXZUVUZWGRPMB"

    39

    Returns: "ABBBCEGGGIIKKLLLMMOOPPPPQQQQRRSTTUUUUUV"

  72. "AXJXLMYHNMHWTYIIYVIZVM"

    12

    Returns: "AHHIIIJLMMMN"

  73. "FEFOBHTIZWOXONCPDPPXFOGEFMZMYXOAMDNSKOQQEWFJC"

    42

    Returns: "ABCCDDEEEFFFFFGHIJKMMMNNOOOOOOPPPQQSTWWXXX"

  74. "ZZZKEDSFKN"

    4

    Returns: "DEFZ"

  75. "VKGTFJJVTQXGEAFDINNOLSXEZORXQBGZTYPWYTIXLLMJWMIGH"

    47

    Returns: "ABDEEFFGGGGHIIIJJJKLLLMMNNOOPQQRSTTTTVVWWXXXXYY"

  76. "ELTSBGXFYCGSSXPMUOSKPAXJRYLEJXWKZMNIVMRZQGJNBOE"

    45

    Returns: "ABBCEEEFGGGIJJJKKLLMMMNNOOPPQRRSSSSTUVWXXXXYY"

  77. "JFXHBZMWMPFOERHXQNEGDBUXOHWDDFTADDPMSV"

    37

    Returns: "ABBDDDDDEEFFFGHHHJMMMNOOPPQRSTUVWWXXX"

  78. "DPRQGPWWVQFBVQGHHJPHLFDAJNQAJSGEQYWHQXYS"

    4

    Returns: "AABD"

  79. "VWPTOJCGJHMUHZTAYLRJGTNZPIKWVPQURSOCJNVMJ"

    33

    Returns: "ACCGGHHIJJJJJKLMMNNOOPPPQRRSTTTUV"

  80. "RQDHVIMPLUBYTMHWGKRFVVWRAVHGANO"

    5

    Returns: "AABDR"

  81. "KJUZTZRTXVZZTOXZASJIAOVKIBD"

    5

    Returns: "AABDK"

  82. "BOUTKWMRRHDNHQUTRLSVDMOHKVJLHJEAZYIYGVLDHEKMVWCJ"

    33

    Returns: "ABCDDDEEGHHHHHIJJJKKKLLLMMMNOOQRR"

  83. "DXGQGSXWEVPXIPMTQVMSHOTAWBZEAFYFPDDSLKMLCBBXWDNFZY"

    38

    Returns: "AABBBCDDDDEEFFFGGHIKLLMMMNOPPPQQSSSTTV"

  84. "HQCHMTKSYHSTHYRTJKBRMWXVRGMWHNSHYYYPIFEWVGOUYFQLBW"

    30

    Returns: "BBCEFFGGHHHHHHIJKKLMMMNOPQQRRR"

  85. "BUVHLGOJJNKPPKOFTFGPVCVKXREAGOAYYHIGBFWFXVIWFRKGYV"

    20

    Returns: "AABBCEFFFFFGGGGGHHII"

  86. "GTZBSGVZTHEVZQIIHRCGAJEIQAUYSXJCIHSQAKUUJMVAZGYNGK"

    40

    Returns: "AAAABCCEEGGGGGHHHIIIIJJJKKMNQQQRSSSTTUUU"

  87. "XTCFVLCNATYLYJKWNCXVJSPTHTLQUCWHDJLTKPOBMZMOSJBFTT"

    18

    Returns: "ABBCCCCDFFHHJJJJKX"

  88. "ISCWEYMYKTKDJIPQODMZBHRSXIPVJRAQHIGKBUWLTTFXPCWQPJ"

    38

    Returns: "ABBCCDDEFGHHIIIIJJJKKKLMMOPPPPQQQRRSST"

  89. "WNNFYHRAJBVCPCXMHTZFTVUIEFOPUSNDILYBVJLWHWDECFQIBV"

    50

    Returns: "ABBBCCCDDEEFFFFHHHIIIJJLLMNNNOPPQRSTTUUVVVVWWWXYYZ"

  90. "DCLMPUPUOVHKXJPTWEMUDOMFVWNWXXDBPFRPZSNQRSIFPPYFKG"

    47

    Returns: "BCDDDEFFFFGHIJKKLMMMNNOOPPPPPPPQRRSSTUUUVVWWWXX"

  91. "WWIVDXKVARTTAIYOXTGHGLWWGVPTERSTGHMELPZBLFIBOEKVQV"

    6

    Returns: "AABBDW"

  92. "CBA"

    2

    Returns: "AC"

  93. "DDDAA"

    2

    Returns: "AD"

  94. "ZAAB"

    3

    Returns: "AAZ"

  95. "GAAA"

    3

    Returns: "AAG"

  96. "BAAA"

    3

    Returns: "AAB"

  97. "RAA"

    2

    Returns: "AR"

  98. "BBBAAA"

    3

    Returns: "AAB"

  99. "KJIHGFEDCBA"

    5

    Returns: "ABCDK"

  100. "ZAAA"

    3

    Returns: "AAZ"

  101. "SAA"

    2

    Returns: "AS"

  102. "ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ"

    20

    Returns: "ZZZZZZZZZZZZZZZZZZZZ"

  103. "LLLLLLLAAAAAAAA"

    2

    Returns: "AL"

  104. "EFAAAA"

    2

    Returns: "AE"

  105. "TAA"

    2

    Returns: "AT"

  106. "EDCBA"

    2

    Returns: "AE"

  107. "ZZZA"

    3

    Returns: "AZZ"

  108. "BBAA"

    2

    Returns: "AB"

  109. "AXC"

    3

    Returns: "ACX"

  110. "ZBCDEFGHIJKLMNOPQRSTUVWXYA"

    2

    Returns: "AZ"

  111. "ZYXWVUTSRQPONMLKJIHGFEDCBAZYXWVUTSRQPONMLKJIHGFEDC"

    7

    Returns: "ABCCDDZ"

  112. "ZZZBYOSWXUMIJFCEXWUOJFEBFUROKQJRGCGSIMGYNOYDFAPFDT"

    8

    Returns: "ABBCCDDZ"

  113. "ABDCB"

    4

    Returns: "ABBC"

  114. "ZZZAAA"

    3

    Returns: "AAZ"

  115. "CBAA"

    2

    Returns: "AC"

  116. "SOPCODER"

    3

    Returns: "CDS"

  117. "RABCDE"

    5

    Returns: "ABCDR"

  118. "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

    2

    Returns: "AA"

  119. "CCBA"

    3

    Returns: "ABC"

  120. "DBCA"

    2

    Returns: "AD"

  121. "ZAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

    2

    Returns: "AZ"

  122. "YYXXWWVVUUTTSSRRQQPPOONNMMLLKKJJIIHHGGFFEEDDCCBBAA"

    2

    Returns: "AY"

  123. "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBA"

    2

    Returns: "AB"

  124. "CCC"

    2

    Returns: "CC"

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: