Statistics

Problem Statement for "FoxAndHandle"

Problem Statement

We say that a string Z can be obtained by shuffling two strings X and Y together, if it is possible to interleave the letters of X and Y so that Z is obtained. It is not allowed to change the order of letters in X and Y. For example, you can shuffle the strings X="abcd" and Y="efg" to produce any of the strings "abcdefg", "aebfcgd", "abcefgd", or "eabcfdg", but you cannot produce the string "bacdefg".


Formally, let Shuffle(X,Y) be the set of all strings that can be produced by shuffling X and Y together. We can define Shuffle inductively as follows:
  • for any string X: Shuffle("",X) = Shuffle(X,"") = { X }
  • for any letters a, b and any strings X, Y: Shuffle(aX,bY) = { aZ : Z belongs to Shuffle(X,bY) } united with { bZ : Z belongs to Shuffle(aX,Y) }.



Fox Ciel wants to register on TopCoder. In order to do that, she has to pick a handle. Ciel has a pet cat called S. As her handle, Ciel wants to use a string H with the following property: S can be obtained by shuffling H and some permutation of H together.
For example, if S="ceiiclel", one possible handle would be H="ciel": she can permute H to obtain H'="eicl", and then shuffle these H and H' together to produce S.


You are given the String S. The constraints guarantee that there is at least one possible handle H with the above property. Find and return the lexicographically smallest valid H.

Definition

Class:
FoxAndHandle
Method:
lexSmallestName
Parameters:
String
Returns:
String
Method signature:
String lexSmallestName(String S)
(be sure your method is public)

Constraints

  • S will contain between 2 and 50 characters, inclusive.
  • Each character of S will be a lowercase letter ('a'-'z').
  • Each letter ('a'-'z') will occur in S an even number of times.

Examples

  1. "foxfox"

    Returns: "fox"

    There are five possible handles for Fox Ciel in this test case: "fox", "fxo", "ofx", "oxf", and "xfo". The lexicographically smallest one is "fox".

  2. "ccieliel"

    Returns: "ceil"

    Note that "ciel" is also a valid handle, but "ceil" is lexicographically smaller.

  3. "abaabbab"

    Returns: "aabb"

  4. "bbbbaaaa"

    Returns: "bbaa"

  5. "fedcbafedcba"

    Returns: "afedcb"

  6. "nodevillivedon"

    Returns: "deilvon"

  7. "bkbkaajaajkkmfmfliffajaelhihlihajaeohggholihoggo"

    Returns: "baaaajkkfmfehhlihjgglioo"

  8. "kcbbdikcbbdi"

    Returns: "bbdikc"

  9. "aaaaaaaaaaaaaaaaaa"

    Returns: "aaaaaaaaa"

  10. "hhhh"

    Returns: "hh"

  11. "adadaddebecbaedeebbadadaddebecbaedeebb"

    Returns: "aaaabbddddebecbedee"

  12. "liahkaliahka"

    Returns: "aalihk"

  13. "ghdhahcfegahcgafhfhabghdhahcfegahcgafhfhab"

    Returns: "aaaabghdhhcfeghcgfhfh"

  14. "lbdlbd"

    Returns: "bdl"

  15. "nssnlatrvxqgdcatobphpnssnlatrvxqgdcatobphp"

    Returns: "aabhnssnltrvxqgdctopp"

  16. "nstnst"

    Returns: "nst"

  17. "kkjolfghvkkjolfghv"

    Returns: "fghkkjolv"

  18. "jbofhjljgjbofhjljg"

    Returns: "bfgjohjlj"

  19. "nfilggcacgnfilggcacg"

    Returns: "acgnfilgcg"

  20. "abhnaccicabhnaccic"

    Returns: "aabhnccic"

  21. "efbaebadacafecabcefaefbaebadacafecabcefa"

    Returns: "aaaaaaefbebdcfecbcef"

  22. "idfbieidfbie"

    Returns: "beidfi"

  23. "cbjfidccahfhjeabcbjfidccahfhjeab"

    Returns: "aabcbjfidcchfhje"

  24. "umnlhebpumbronkquumnlhebpumbronkqu"

    Returns: "bbkqumnlhepumronu"

  25. "uliwgjuuliwgju"

    Returns: "gjuliwu"

  26. "bncmhohshdabncmhohshda"

    Returns: "abncmhohshd"

  27. "cbbbabbaaacabcccaacabcbbbabbaaacabcccaacab"

    Returns: "aaaaaaaabcbbbbbcbcccc"

  28. "pngilmanqiodjmjqlapngilmanqiodjmjqla"

    Returns: "aapngilmnqiodjmjql"

  29. "aaabbbaaaaaabbaaabbbaaaaaabb"

    Returns: "aaaaaaaaabbbbb"

  30. "feekcffkfeekcffk"

    Returns: "cfeekffk"

  31. "bfebaabfebaa"

    Returns: "aabfeb"

  32. "hoiphoip"

    Returns: "hiop"

  33. "dfcqqdfhjenirnllhbmdfcqqdfhjenirnllhbm"

    Returns: "bdfcqqdfhjenirnllhm"

  34. "aa"

    Returns: "a"

  35. "caefdedcdecaefdedcde"

    Returns: "accefdedde"

  36. "kmmllclfimjaidgkmmllclfimjaidg"

    Returns: "adgkmmllclfimji"

  37. "aaaaaabaababbabaaaaaabaababbab"

    Returns: "aaaaaaaaaabbbbb"

  38. "kbsouijvfaabvkbsouijvfaabv"

    Returns: "aabkbsouijvfv"

  39. "smweaamsmweaam"

    Returns: "aamsmwe"

  40. "chch"

    Returns: "ch"

  41. "ff"

    Returns: "f"

  42. "bbababbaba"

    Returns: "aabbb"

  43. "cbdifojmjbndocbdifojmjbndo"

    Returns: "bbcdifojmjndo"

  44. "fkcbejiafcfjcjimmjjghmdeafkcbejiafcfjcjimmjjghmdea"

    Returns: "aafkcbejifcfjcjimmjjghmde"

  45. "hgdifclibebibgjglkjnhkbhgdifclibebibgjglkjnhkb"

    Returns: "bbbbhgdifclieigjglkjnhk"

  46. "aaaaaaaaaaaaaaaa"

    Returns: "aaaaaaaa"

  47. "bhigdikmkgdipbkibjbhigdikmkgdipbkibj"

    Returns: "bbbhigdikmkgdipkij"

  48. "acabacab"

    Returns: "aabc"

  49. "ee"

    Returns: "e"

  50. "bgbg"

    Returns: "bg"

  51. "hnpbafrebbhnpbafrebb"

    Returns: "abbhnpbfre"

  52. "thcgupthcgup"

    Returns: "cgpthu"

  53. "accbabadeeaccbabadee"

    Returns: "aaaccbbdee"

  54. "fokgpenjjlrefajhepfokgpenjjlrefajhep"

    Returns: "aefokgpenjjlrefjhp"

  55. "ljombhhosdhcpmnolibgdkiljombhhosdhcpmnolibgdki"

    Returns: "bbdiljomhhosdhcpmnolgki"

  56. "jlpomfbglenmdqcjlpomfbglenmdqc"

    Returns: "bcjlpomfglenmdq"

  57. "hshs"

    Returns: "hs"

  58. "cohvhooorsffjrmmontivbjcohvhooorsffjrmmontivbj"

    Returns: "bcohvhooorsffjrmmontivj"

  59. "icejddraacdpliiefpegrospicejddraacdpliiefpegrosp"

    Returns: "aacdeegicejddrpliifprosp"

  60. "oo"

    Returns: "o"

  61. "koseomlnmohajlbnbphghkoseomlnmohajlbnbphgh"

    Returns: "abbghkoseomlnmohjlnph"

  62. "dsds"

    Returns: "ds"

  63. "kefcfgicdjbbahikefcfgicdjbbahi"

    Returns: "ahikefcfgcdjbbi"

  64. "ghgh"

    Returns: "gh"

  65. "khhejxlkxmpjmsfitdgkeqkhhejxlkxmpjmsfitdgkeq"

    Returns: "dekhhejxlkxmpjmsfitgkq"

  66. "jobgncfidoaanmomnhcbhakjobgncfidoaanmomnhcbhak"

    Returns: "aaajobgncfidonmomnhcbhk"

  67. "gvhfhkuivvufuhpbgvhfhkuivvufuhpb"

    Returns: "bgvhfhkuivvufuhp"

  68. "nidbednljlkcnmdmljlfbhbnidbednljlkcnmdmljlfbhb"

    Returns: "bbbnidednljlkcnmdmljlfh"

  69. "fbeiibfbeiib"

    Returns: "bbfeii"

  70. "qtptpsdtgcekqtptpsdtgcek"

    Returns: "cekqtptpsdtg"

  71. "qrnjnqorrgkakenlcrlllqrnjnqorrgkakenlcrlll"

    Returns: "aclllqrnjnqorrgkkenlr"

  72. "nrdbqiinjaqomibodlilsbnrdbqiinjaqomibodlilsb"

    Returns: "abbnrdbqiinjqomiodlils"

  73. "qieppnjcskjplupeamgqpqtqieppnjcskjplupeamgqpqt"

    Returns: "agpqiepnjcskjplupemqpqt"

  74. "ffjaibhcglhkiffjaibhcglhki"

    Returns: "abcffjihglhki"

  75. "hqchbpqghmvpgcepdnvblhqchbpqghmvpgcepdnvbl"

    Returns: "bbhqchpqghmvpgcepdnvl"

  76. "ccfcccdcfdeddcaebfbccfcccdcfdeddcaebfb"

    Returns: "abbccfcccdcfdeddcef"

  77. "opoepcibabfpbjdickiopoepcibabfpbjdicki"

    Returns: "abbciopoepbfpjdicki"

  78. "wqgrftamjcgtammulqabmrwipwqgrftamjcgtammulqabmrwip"

    Returns: "aaabipwqgrftmjcgtmmulqmrw"

  79. "mftoncoadnibksdfmftoncoadnibksdf"

    Returns: "abdfmftoncodniks"

  80. "greqceanereokwhvptuaiqgreqceanereokwhvptuaiq"

    Returns: "aagreqcenereokwhvptuiq"

  81. "dd"

    Returns: "d"

  82. "kihmilalfmkihmilalfm"

    Returns: "afkihmillm"

  83. "eobkhpceobkhpc"

    Returns: "bceokhp"

  84. "unlgmoxnomsinlunlgmoxnomsinl"

    Returns: "gilunlmoxnomsn"

  85. "kdqqrjdejoqlinkdqqrjdejoqlin"

    Returns: "ddeikqqrjjoqln"

  86. "fgacafhffcaceebfgedafafgacafhffcaceebfgedafa"

    Returns: "aaaaafgcfhffcceebfgedf"

  87. "efdeefde"

    Returns: "deef"

  88. "ebacaeebacae"

    Returns: "aaebce"

  89. "aohjpioefipaohjpioefip"

    Returns: "aefiohjpiop"

  90. "ccbabbaaccbabbaa"

    Returns: "aaaccbbb"

  91. "alcfickgoajhfcihalcfickgoajhfcih"

    Returns: "aachlcfickgojfih"

  92. "bealcdbhbjefcfcbealcdbhbjefcfc"

    Returns: "abbbelcdhjefcfc"

  93. "phddddanqnhqqrkamihkaphddddanqnhqqrkamihka"

    Returns: "aaaphddddnqnhqqrkmihk"

  94. "hmlhicfnihlonninecfoohmlhicfnihlonninecfoo"

    Returns: "ccfhmlhifnihlonnineoo"

  95. "jcjlnkkcamahcacjcjlnkkcamahcac"

    Returns: "aaacjcjlnkkcmhc"

  96. "bcbecfdicbfgchccfaefecbcbecfdicbfgchccfaefec"

    Returns: "abcbecfdicbfgchccfefec"

  97. "cjaffaknjkcjaffaknjk"

    Returns: "aacjffknjk"

  98. "jgbbbiaaeafacggcbcjgbbbiaaeafacggcbc"

    Returns: "aaaabcjgbbbiefcggc"

  99. "ccbdccebheihcbefcdbhhbgccbdccebheihcbefcdbhhbg"

    Returns: "bbbbbccdcceheihcefcdhhg"

  100. "nbnknbnk"

    Returns: "bknn"

  101. "afbacdbeafbacdbe"

    Returns: "aabefbcd"

  102. "ldmeqhgnrrfocfhfoldmeqhgnrrfocfhfo"

    Returns: "cffldmeqhgnrrfoho"

  103. "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

    Returns: "aaaaaaaaaaaaaaaaaaaaaaa"

  104. "hfcchijgdajffcdcchfcchijgdajffcdcc"

    Returns: "accchfcchijgdjffd"

  105. "fqatwhboemrpxauxmxlfqatwhboemrpxauxmxl"

    Returns: "aafqtwhboemrpxuxmxl"

  106. "dgdeafheiiebdfhkdhdgdeafheiiebdfhkdh"

    Returns: "abdddgdefheiiefhkh"

  107. "dqbqfrchfombkgdqbqfrchfombkg"

    Returns: "bbdqqfrchfomkg"

  108. "bbbaab"

    Returns: "bab"

  109. "foxfoxfoxfoxfoxfox"

    Returns: "fffooxoxx"

  110. "zzyyxxaabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvv"

    Returns: "zyxabcdefghijklmnopqrstuv"

  111. "fkhtbqsnuegusptebdgbhbfolnqpbdltrohkbmbsrnlbhsltmn"

    Returns: "begubbbflnqpdltohkmsrhstn"

  112. "baba"

    Returns: "ab"

  113. "mqxmhlvqczcaqzlyezvkqnkkcxenukqjjqeazcvueswvhwsqqy"

    Returns: "malezkcxenkqjqzcvusvhwqqy"

  114. "aabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyy"

    Returns: "abcdefghijklmnopqrstuvwxy"

  115. "ccaacc"

    Returns: "acc"

  116. "adefghadefghciklomciklomprtyuprtyulooppoolyurttruy"

    Returns: "adefghcikllmooppoyurttruy"

  117. "zyxzyxzyxzyxzyxzyxzyxzyxzyxzyxzyxzyxzyxzyxzyxzyxaa"

    Returns: "xxxxxxxxzyzyzyzyzyzyzyzya"

  118. "zzyyxxwwvvuuttssrrqqppoonnmmllkkjjiihhggffeeddccbb"

    Returns: "zyxwvutsrqponmlkjihgfedcb"

  119. "zyxwvutsrqponmlkjihgfedcbzyxwvutsrqponmlkjihgfedcb"

    Returns: "bzyxwvutsrqponmlkjihgfedc"

  120. "abba"

    Returns: "ab"

  121. "abbbacaabc"

    Returns: "ababc"

  122. "azzzzaaa"

    Returns: "azza"

  123. "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

    Returns: "aaaaaaaaaaaaaaaaaaaaaaaaa"

  124. "yxwvutsrqponmlkjihgfedcbayxwvutsrqponmlkjihgfedcba"

    Returns: "ayxwvutsrqponmlkjihgfedcb"

  125. "ppaappbbllaallbbllvv"

    Returns: "aappbblllv"

  126. "jjhsrrthqbteqytyrwrsxmnoeegtrgaxbmkwepkazpinlizolr"

    Returns: "jhbeqtyrrsegtaxmkwpinlzor"

  127. "zzbccbaa"

    Returns: "zbca"

  128. "aaaaaaaaaabbbbbbbbbbccccccccccddddddddddeeeeeeeeee"

    Returns: "aaaaabbbbbcccccdddddeeeee"

  129. "bbbbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaaaa"

    Returns: "bbbbbbbbbbbaaaaaaaaaaa"

  130. "bccbaa"

    Returns: "bca"

  131. "zlnyznttyl"

    Returns: "lnyzt"

  132. "bccaab"

    Returns: "bca"

  133. "hnyhbxibuamwukxaymuncubdakwbatptihydkhkpjbzcpbpjyz"

    Returns: "akxamuncubdkwbptihyhbpjyz"

  134. "hebhajejba"

    Returns: "bhaej"

  135. "jihtsiigtisajsgojthuqtorrfnmntnrfnnnqagtmusourgjou"

    Returns: "higiajsgjqtfmntnrntsourou"

  136. "bbbbbbaabb"

    Returns: "bbabb"

  137. "nacnbacb"

    Returns: "acnb"

  138. "aayyxxwwvvuuttssrrqqppoonnmmllkkjjiihhggffeeddccbb"

    Returns: "ayxwvutsrqponmlkjihgfedcb"

  139. "afgzgfgaffgyyggafayafgayayafffzfgzyyzzyzgzyyzzagza"

    Returns: "aaffgaaafgffgyyyzgzyyzzgz"

  140. "babccbaaba"

    Returns: "abcab"

  141. "baab"

    Returns: "ab"

  142. "nazmysmosnmfjlnxjcgoraopzpnnxjpbmflnagpfbyajocfryy"

    Returns: "ammosaopznnxjbflngpfjcryy"

  143. "abzjubzuwebdehbwzwqkhfbjptkfkbwbfdbjbkzfpzfjzbtfqa"

    Returns: "abbubdebwhbfkwfjkzfpzjztq"

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: