Reverse Shuffle Merge

심심풀이로 가끔 가서 노는 사이트. top coder의 easy version쯤 된다.
https://www.hackerrank.com/challenges/reverse-shuffle-merge

아직 어려운 문제들을 많이 접해보지 못해서 그런데, 이 문제가 지금까지 해본 것들중에 가장 시간을 많이 잡아먹은것 같다. 선수들은 이런거 10~20분에 끝날텐데. 답안 보고 좀 더 생각해봐야겠다.

테스트 케이스 세개. 문제 / 답 순서.
bdabaceadaedaaaeaecdeadababdbeaeeacacaba
aaaaaabaaceededecbdb
djjcddjggbiigjhfghehhbgdigjicafgjcehhfgifadihiajgciagicdahcbajjbhifjiaajigdgdfhdiijjgaiejgegbbiigida
aaaaabccigicgjihidfiejfijgidgbhhehgfhjgiibggjddjjd
cttpuwqslbtttyukcoorjbootbyrsktwxwmqtwrqrwqwctktuwtjtblwrujywyoyolkusucjuoyowswotckwultobwpwyuqymyuqxouuwuxwboqwykjuwjuukmkuytuquyubtpcytoqsyctwwtwrswptrroktmcwpstttblpuylsljmwjyqwtptktbjotqttyybyybyywlwtlyyxtqobttcuwxylswtytrcoytwtbuowkruoystqyyptwuuxykwljsuyutyboxwsutouruublwxowmomwmuoruwmbcustubtmmutswqtlmxuoyurumuwurpqsrwbltcoopyuckrbkctcqotwboxmjskcttwwrwlqptttlsuuymwuuucytytkmwutytlcojwswqlytyjwluwouuwcuowttoorwojuqwytsokwxtmtkoxtkwujsujcotbjwwutymwcmkoptwstywtwktowwwwutyckukwcjortwltocjpwwqtmmwjtwwpmwmbotsjulllmjsxwtlrpbkytwqttjuoowkuctqtwruowuwocwlyxylkroluysyktrmbtwwwkoswctojubrywpsxswqtptwcsbpmwourutttsluoocjwbcutwoptpcwjtpyubwtktuoytwytukrwtpuoktslxbspwymmuuuosluywtoyttwyujottrorcwtyywwwmtykyuytrwbwyoywtywrbpjwrkymlrwktwmwjrtwttwwwycswwuxsywrtutbptsowcucxuowuuwtrytuywxwtwuwcwlttqurottykbbwlbcxttoctwbxrurbxcrtqsyyucytwxpcuwywbbwskobwwjqjtsttsocwwxuryjputpwktjkoutyukywqywkspwopuroybqtyyokywultwmwomwxttbwwcutxoycotbptsttbwtwqutywjlxbpoplywljkqkwxttooqwwxtbtbccmbsocuuuptjultbowkuwpuspruqtoupltwmoutlyjjjqkxlwptctwwywtwjbcmuwkbltwyuormsuwtwxpxkkycspjjpmokuytbcowxxpuwwtxottjqpotwoxxwkwqwwswtwlowryplsoctstyorywyrlyrlltuyqtmowjpxtkttkowmtuttbolwpouwtxwwupucuuujckubwkuywkswkxuuybpsckuworqupqktujywwcywtuttbccottpuywkbukuwmjtsputkyjyrmwusllcbttlusmwwymybqwokspbolspokuwwwotrbwtwtopqpolsqrwkwtjottputboptuurlotxsttyywcktyymltmywobwwtpooqtopcbktbxcuwtxuuyyywulcqwxqywtkckutrtsttxtkyoccumttuwsumutrwryqwxktyjoxbtcuwmpjcqcwpxmwlumucstwykxoquylwxtuypwytkwkyltmtybsbywrwltytutyuruumumulpytouwttbuxtrlwkrowwywtywtjotbbosjwtutctuxutjbopywjturtqotubjwcwwtuymtyypxtyouubpjuotowsbcoowkwrwutwyuprltwuoquowurujtusutuwywtkpbwjoytcouyscbllrcoowmwbttywwwubpxptmstwtwwrutlmywmtbyucyujywqtjuxoltkwlsmuylwjktobwutyrpoxtwuytuuqclytutswwkcwoytuuywqrlyywsquypkltskwuoctmwwwwttwrtttuctcpwtkmjuqyouuoutjusuusuctwytkwcccuyylyluwxtocttrotywybwwmlokywtywurpocyttcrtpwwrqctwoxtrupoujqyutsqxtssurtyoqwuupwwyowtyutywtqyowjwwyukmqwuctjmtouuttwytwsxtlrurxotrttupswttjustwswtjxscjtusywwswkwpxkkcykluwyuruqtwwuwuutsubctmuprobjswmbstuqjytuytrtlbsytupubjyswrmoyowjwywxolqxukuwtxkktouccuomwptwtuctutwprubswcxscwcmcostwwttrumtoytowwulotwsqujrmopubuusuuwxwqwwlmyyttttklbtxoxwxttjwmwtumtptwlbuouowpswcytotropsuwwtmwuyutkryrwwtyxuyyyywwwyuttwucutcctwwtjjtxtmwttwoubtcsytwucwsbupttutjwwtxwutmwqttowwuxsbokkmujtwwuctwptytuwwowpwwoxoowtjutwruttcwwmbwowttplttbpubxlyuojwurwxptrjttwuyqttyuttstwotbywuwymtottptlsrbxjutbubtypwbcttjswuwywwutklttxwttttyukqpttykjtcwwpyxuxyopsswmxbyyulwuctokouwwkyowcwcwmsrojmswwbyokwyywcuwlxoymsrbbruotwotcwuqtwuqwqyuuytbsowbwlubyywxkwupuyosoxmsuqsyucqctwmpokstwtcrwytuuwjmupwtoowtycuockpxsypstktyttxkltycbpsrwwtuxqpommwwwtkmwsjmubuquccwwslwtwotjtwwtukowomojbwubwttptoowtubrbwrycxcpotttwjpooutuowbotuwuwjysuwsjlbtcstwbbwpobuyxstyjuxtjrutjtuuwustorprjuwbwsttkwuuwwwpmjcuctlowkxwwmttwtwxqmywusmyorjtptwoyswwqbpywkwkyxttocmcwujtqcrubskqjtoujouyuwtpmucutupcqttjymtbywtpyytotcluwutkyljmpqyowupsuxmuusjtkwwcqstjqwwruttcbttcptctowtomtuojoywutuktwwwoortpmxubljumwslocurlwttooustwyqptylytpmxukwytxrojltubtuusyttutssmkwyqojtrjquotwtwwppwwmctwytyytwtclkworwwbtusryuwowkostwwwwwwmxowbmoltutystxmpwwttttltyqxoybbutmotwqqutxprkmoyomqbjtttuupmjlpmwwxsstcottrwttlrwwptsybywtobwotoxxybowxurwroqcsyrpoqwuwuttutrmwwytwxuwkutbrtmmuosywobtuctcuxpwcxqsuowutusmywsbmttsyuuuuuttttwjtopytljomywtotytuuwsoyjkwlooowlyxxtopyyuwyutctjukubyqxpurwbkurwyrpswmktuubxooyqktcboucsywolkwoqoymtjktwoqrourxubuwwywlwujjwwwqwpyxuwrykujlutqocmwltpcmxstoxklqtutsotoxyututwtwtwwrwysumupyrwxlwwmwslslwboxwtbtlpwlxyqlttjubptmytmwbsoyuwjtttwlwpryumxkpcowkujowtltywuolwwotyutucysuqltttwjutoucowtpttwtwltjsostwwoktkwtwtptwrtyjobtutqrwwqtyqtuwyomttmymkqtrrjtwtyuxtxlutotpwyjwsojwtmpstrooowwocrwywyxpocuktmoylupstrpccooptucmtybwxowwuruulpywqpwkqtowswtttcromumuwbkwctpckqbyjttwrjbtxpwpwwjtcmwtuwcbxcxyuqttsxjtpulumwptoxmxyqybwcjpkuwcoxcbwtcowypttuquuosyurucbtywykwtouwtrskbltuwtjybtmquytjyxtkucscuwulwjxwbbwotswpqqkrpybuwwumtpoxlwykqurqcukrmutucctowytwtbpxwbjojkqwuyklwttytupqwopoqyyqmoybutbwuywujwqbowwlywmwwwumbcwbytusortwwuqmqbulwtkouqmutotstomwmbylwrkowwusrqcyboouwwklytowxwkttsrwootqxwswtsjwlolqobtucwpqwotpuqkwjtlcucwjjtcmkkxurybukqtybjjxuwttquswytojtwbytxwubuttuwtwswlwytmtquywtuuwupmwubqtuuxctottkojqbtxbuyqwsquutoqwctwwuwrwomtwowttuwsywuykuttwruoppwumutltwttwstusxuyqotypujtxwtuwukqtmmtuuywuctqyrttptpytbloplsmtuctmryoctqmtuwtoytmwtuopjkwtutckckswswowoutulxjwlosylyjuutttjcwuwousrowttwlwuxqqobmtwmcttwyuxubryjkoouossyjpoqrxrtrmtrsotbyplwrwtcypmqcttousypyrokscyjropxwtputjwyylobttwouuustqtrcwowysottptyoktuwspkujubyrtwtqutwqsbkuuccyjlmltblrtyqwxtuxbukmuoptojwcrtsocbywcttulmtukjqtsuswwuyuttrkywuwqqcpcruymkxoltyxwrsqcuotkwkwtroclumrxyulcosrwowutouqxttlwolkkquqtrouuuxswuwtotypulrkurltuomwubpymkwuttuwtwywpouoswtkluytttywutwwwytwumxpktquoutrotbbttuxptuouqwwmtutuussuttspruwouyolxqwtpyxmlylcwwrlktypwtulwwyqywjpluoswpyqtmpttouptstwxurtruwpjojlwtwqtsctoutsswyuxpxbtwwotyjouubwwuttbkuocootswcktqbukcbywutjwwmwukrljwyxwkqwlowmkwkpcmumtqwowkytlrwycyuwtcbyutrxrowtstytckqyubttotltkmcysuskrbtucttxwluulsttjutcjskmwklrymwutcuustxkwmyycbqjlquwmqwjwutwuwutwusosclkxtktjompkoputtobqwmlqljxltuojptkcwmcqpttoyjuuosltwloubrjwjttjtwttuwuoctsttowwwwjybytqmoqytwrtctswworbtjruluyoktlwtswtrwyjxtjtttobtpouuyutlqcotslrcwmkbwjtstwxospqjtlbkuujouoowtcywwuwjtpqjutwtotbqcwytbswuubtuuwbbjjqboutcuosuwtrtmtpbxpytutowybjwxuuwwtotwuxtywubwotutmtpqcxoyuucyowuxqtcwtltpslcwyuuucwctpowsxrtsssuwycywrtutrjbccmblytwtktltucmjtywwupxtttpyrtmtuytcbwymtybyyllrsujtrtjoucwqyxtkuywtcwotuxbmtxsuwwyqurysotccrwrttrqjwwumrtlwmoottoywurjcrwttyyutcwmotmkusotcrbwrltswrwjupwowlykwywwlwqttttwcuxttbuqtutsoclutyyuwwwklbupwybrctbpsjwybjqwobttlxywwwwjuwxorowyrurwywoocwwwtbkpkuourokpttxqsxpyrloryuwlwwwkwyutuqluwuowwtywttywtutoulotxwluwwtbottuowsuqltuwrwkbjwtwptyytpxttwkmyutyqsyobocwbtwwtwutwbpotyupocuwwrpqyjpoypwwomtolwqwcstymuulmxuuuyllpcwcppqwkcwubkjjymuxtbuuoytuyyoubbjtpyutwkttycywtykwttqllmxpuslkxutowkwusuxmqooxptmmcsorryqtuwuuxcjctjwywyjwmyuwtsxtyowbrjwutluqkkqortwtcrwsskkytytummwymlstwqykwuttwpjptyuxwyltyxubustwsjytooqmpctkpltwutotkbtpyjsuwkuquowmuwpjtwtmcmtsobwttoqcstwcqyjcuttjbkowwsutwswjqmtrotutwpluotxtrqmwjtbuwjwuwtttbtkwkomwqltcwtqkouojcttccuttuwkwwotbxurwkowtmtxmuwswpotwwtykxcucsuuwtsbpwbsuywjwboqsurxotrtbukplwbttyptuwuwwwoutusbwtytwtuwxtrspwutwxrutmwwyxtmpupowtrbwxwtywcxyljtuwtuttlpulctrywwttrwspyomottxjbmuysotqckrbyljyrukpolmkxwbcojcloycryybtwlqmyuoluwoqqbwwxjuxltpwrtyocowqkbqttujyrwyrtrqtujumrutlyuumurcwttwcoyqpwkumctwbtxjsktwwpwturbybuqwwotwuwwtwkstjmkbtymtbyyyrxtlupwyyyqwbrpurttmwuujuyowwwwottrqpwjuwutbtkjytrmwqtuoyyqbypwwwcxwtukowmuyotpwyjwoyouspbuluurtwuwtlwxjkscutukolcmtxtotkpjuoctuupxlslkswqwwoycrwttquooyuwlystuttwuctkyoobojyrcutowkpowwmwcomtuusrmosyyrxubttwcwuljutrotuxtttotptoowsuctojbcucrwyycouoxolktsyupswuytwbwtkwwwtbuwtxtcwtwxyywxtwctuqtwyytjtsokwtuorwwwoututttuuuttotowtotkuouwpwyujtooqykwqtuyuwypuytybouwotmtuwktowcwywsytutwtptpjjwmjktxtswqccmotbbwqyytotwrltrobcbcblyowtbxucwobmttwxscyoccwyluxytbuxwmjrmqmutttlmjyookywpqjwoxkwtwuwutotbsywttuyslbwuymouupwmbbxtubuypuyyyxrbtwwpqwctwuusqoytwytuoqkwjorjrqmttckrwljbuwurwtupuqybwpuukwtuqmwwwmwotuykyorsqqtwyypbobmymjukrwuwswoqbtxppyblbwtmjtutxcususootbytuybljlstttjtjyuwcwsoukwtuuywjkmbwpxoywytmoxjsmlmwjjojukstussswkoyllltpuwywtmtcwwwyosttlrrmsrultqpucqsxplxuslupqutrtybtowttuyxwwwkqtwyypytmuctuoxltwpwwyrtjubtuyuyytroloobyumqttobrtwcuxcccbqrjwuuttuykwubkqloootwytctxwypcutxuwytswttwbptrbwtyqtbmtwoxtcwccmotwrtrxoqcxuwmoootuqujubottxwkokcwycyqtqwuwpxyymouctrywuyktytlukujssuktwowwyctrtwtywlcctkttujpyrpkotqcwmrwwttybmssmbjwussbutmuluttutulmswlljtuxbwyujwkytytmxyltuxwtuomtoourswuuoyupkojlulutuktubuxwxttyquuxylwsumcuotwbuuukttttwjtjobtyjtusuoubctmtwwwswlcxpsojculowxcuwutktkwykwuwxkwotclccrwwwxwtjutotmtbtosusqtruobbtotswxtbrruywbwuwrctwysxjmlmsytljutmowwyqpwtjotybcwyoutyxqojxutkytqcctwmrwrubtwwutctkttwutwolwywrtrwmboulwtjcwubtoooxboutopswbqytywmwtwwqwptcottwwoscrytttwuomscbbbjqycuuomxusuubwxyctsowrpouqbjwwwxtuwqwstwjssckxoywwmpcrsttupuoqquuuqwxywrupuwktcttuukmcwuyuuortwysbtpqtttlqrtysssuowstcuwowupklokmcxuususkmktsyywkbwqkmtlbtkcwwouckpxjwoxujutkuttqmkwwqltpxwuuklwoojtcmtotkuqtwsytytructwjosujywwlsxyqtputyqryyukxupwtymwokyywuytoorwlpppybtpqstjlowswuwlywuwwtcpybjtostwwoqlwbwoklwlttulutqwowtqywwtbkwlwmwowtwwtupojwjmtwwpkcwcywmywuustqowtcttstyuqwtyllcywctmtywwqolrbjuostswtxttusoucmwtltsqckowwoupwywswllwotostlwsrjbtppwbobskcmsttmkuyowjtwctsomxoyttutlpyycxutlxwytmjuuoscuuqpwwttwwtwwlwwwkbowwttbtscuwmwkourboqqowlwqkpytwtocrtwbuyktqtlouxoomurructtlycywxswwpyustwmrswymwmwtqotuwowuwwbswbkpuwtrpuolsjyluquwpcwoywbpubpjullckkyxpwttypturwuutrrtwucsrstcuuuroutwmtxqyytybkpwjtlywjytumkwwysruumtcwycuuwqbrttxoutorwlumyyuoouoccwsptyqtyusukojqutrppjuosubwmwwpooquktyuybutpwbouwjtmostrtwqwwmbtoqyokputwtjbptywkytjbttqwwyukotlwoyoyopwtorxkjwuwttwxtttypktuclwtxsckoqtxytwtlttoctlswtqbucwkbwubxotkttcbtutottcttpuybqlwrojbwwoqwobysmxtpobltjoywlwkptukytpttymtltsxlpqbyuwlmycummltwpptttpwuwjojjwwsrqujyuttuujoopkjcuputjqwxjotcsbqwrottbtjwrbycoqbluyoutwtotosmktqtwtqwbsoxycurrxstjowuwuctjucjrtuwxskqjktuoxlqkxwtywrwwucbtukworttutprcbwsouupxytwmutuwykxwswrtulcywywprpotqcwsxosutkombtscotccyostwwtwrwuwpsujlwbqqrmutjrptxrtwoxcxuyptrkuuwxbuoywyrwmttujruwopowwuttkwwuuwtoqwctqwutwuttcxqbtcbyjtrotyskxqpxmjllumylcjkwlcotljqkyjsyojkowuturuojltwtolmmwukxbtksxsujuswooupttjtutyoupwqwutwmysupkukoyymywywomwwwccomtbcxyoqucjyjpwytybsowjkxytyttwjylurpkrtttsqttkutrtuwuwttttmuwxwxutookorcwkwstwttxuyywkuccwtwwtuuwyooktytktjutsousjbqulmrxwwwjwsocqtwwpttoykwypptbwjptklwlucrmbcwkyutobtwucwxlywxrsruywyumowwtmjbsmjjrtyblyttcwoutwtqsyxxultuyuqwrqwwupmqwwotsytomjqtcuwutscxkokwxwtttubuwjtujxttluuwwotwruuwywcktkmyryywtusotjttouwowbuuwtwjswuwpocoucobkrtwttytrywtwttulbxjpywsosxtbrocjuptytcwttmowtsuwrpjpmumqtljwjclttoquuprwjwqswutjbwtwtbortwcbtxtwswswpopywbcouwtwlbujxucyrwctwuyjptutowksyutkrwutupkklwojutucsowquttsulllwxppotuoktubrtopttmkbtmwmwkttopwpbkyxbuwkbjwyutmtwotsostswuxyjqqwlxutucltutxwtumyopjwlowwwttuwtopotuulwuowutottkppwotocwwxtbcusywwqwxtwtkytquttuwyujttusqwwcwmpttcllyrsxwuobrtmtbqptwqytplwyuwmtyltbcrwubrwxtwtqmkwkwptkmuujlwutqukwpyjrtxwsstmutuqytmpxkypulwortyswtuxwsukyruqbtostbbtyyyubttusjukwmmwstcyo
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbccjjcjcjtjjltjottccktjotjlqlmqottjtktcosttjqmqjqcmwkxtctuwlkwjctujttluulwxttcutrksuscktltottuqcttstworxrtuctwucwrltkwowqtmuckwkmwlwqkwxywjlrkuwmwwjtuwyckuqtcwstcoukttuwwuujytowwtxpxuywsstuotcstqwtwljojpwurtruxwtstpuottmtqypwsouljwyqywwlutwpytklrwwclylmxyptwqxloyuowurpsttussuututmwwquoutpxutttortuouqtkpxmuwtywwwtuwytttyulktwsouopwywtwuttuwkmypuwmoutlrukrlupytotwuwsxuuuortquqkklowlttxquotuwowrsocluyxrmulcortwkwktoucqsrwxytloxkmyurccqqwuwykrttuyuwwsustqjkutluttcwycostrcwjotoukuxutxwqytrltlljyccuuksqwtuqtwtryujukpswutkoytpttosywowcrtqtsuuuowttolyywjtuptwxporjycskorypysuottcqmpyctwrwlpytosrtmrtrxrqopjyssouoojyruxuywttcmwtmoqqxuwlwttworsuowuwcjtttuujylysolwjxlutuowowswsckctutwkjpoutwmtyotwutmqtcoyrmtcutmslpoltyptpttryqtcuwyuutmmtqkuwutwxtjupytoqyuxsutswttwtltumuwppourwttukyuwyswuttwowtmowrwuwwtcwqotuuqswqyuxtqjokttotcxuutquwmpuwuutwyuqtmtywlwswtwuttuuwxtywtjotywsuqttwuxjjytqkuyruxkkmctjjwcucltjwkquptowqpwcutoqlolwjstwswxqtoowrsttkwxwotylkwwuooycqrsuwwokrwlymwmotstotumquoktwluqmquwwtrosutywcmuwwwmwylwwoqwjuwyuwtuyomqyyqopowqputyttwlkyuwqkjojwxptwtywotccutumrkucqruqkywlxoptmuwwuyprkqqpwstowwxjwluwucscuktxyjtyuqmtyjtwutlksrtwuotwkywytcuruysouuquttpywoctwcxocwukpjcwyqyxmxotpwmuluptjxsttquyxcxcwutwmctjwwpwpxtjrwttjyqkcptcwkwumumorctttwswotqkwpqwypluuruwwoxwytmcutpooccprtspulyomtkucopxywywrcowwooortspmtwjoswjywptotulxtxuytwtjrrtqkmymttmoywutqytqwwrqtutojytrwtptwtwktkowwtsosjtlwtwttptwocuotujwtttlqusycutuytowwlouwytltwojukwocpkxmuyrpwlwtttjwuyoswmtymtpujttlqyxlwplttwxowlslswmwwlxwrypumusywrwwtwtwtutuyxotostutqlkxotsxmcptlwmcoqtuljukyrwuxypwqwwwjjuwlwywwuuxruorqowtkjtmyoqowklowyscuoctkqyooxuutkmwsprywrukwrupxqyukujtctuywuyypotxxylwooolwkjyoswuutytotwymojltypotjwttttuuuuuysttmswymsutuwousqxcwpxuctcutowysoummtrtukwuxwtywwmrtuttuwuwqopryscqorwruxwoyxxotowotwyystpwwrlttwrttoctssxwwmpljmpuutttjqmoyomkrpxtuqqwtomtuyoxqytlttttwwpmxtsytutlomwoxmwwwwwwtsokwowuyrsutwwrowklctwtyytywtcmwwppwwtwtouqjrtjoqywkmsstuttysuututljorxtywkuxmptylytpqywtsuoottwlrucolswmujluxmptroowwwtkutuwyojoutmotwotctpcttctturwwqjtsqcwwktjsuumxuspuwoyqpmjlyktuwulctotyyptwytmyjttqcputucumptwuyuojuotjqksurcqtjuwcmcottxykwkwypqwwsyowtptjroymsuwymqxwtwttmwwxkwoltcucjmpwwwuuwkttswwujrprotsuwuutjturjtxujytsxyuopwwtsctljswusyjwuwutowoutuoopjwtttopcxcyrwrutwootpttwuwjomowokutwwtjtowtwlswwccuquumjswmktwwwmmopqxutwwrspcytlkxttytktspysxpkcoucytwootwpumjwuutywrctwtskopmwtcqcuysqusmxosoyupuwkxwyyulwwostyuuyqwquwtquwctowtourrsmyoxlwucwyywkoywwsmjorsmwcwcwoykwwuokotcuwluyyxmwsspoyxuxypwwctjkyttpqkuyttttwxttlktuwwywuwsjttcwpytutujxrsltpttotmywuwytowtsttuyttqyuwttjrtpxwruwjouylxupttlpttwowmwwctturwtujtwooxowwpwowwutytpwtcuwwtjumkkosxuwwottqwmtuwxtwwjtuttpuswcuwtysctuowttwmtxtjjtwwtcctucuwttuywwwyyyyuxytwwryrktuyuwmtwwusportotycwspwououlwtptmutwmwjttxwxoxtlkttttyymlwwqwxwuusuuupomrjuqswtoluwwotyotmurttwwtsocmcwcsxcwsurpwtutcutwtpwmouccuotkkxtwukuxqloxwywjwoyomrwsyjuputysltrtyutyjqutsmwsjorpumtcustuuwuwwtquruywulkyckkxpwkwswwysutjcsxjtwswtsujttwsputtrtoxrurltxswtywttuuotmjtcuwqmkuywwjwoyqtwytuytwoywwpuuwqoytrusstxqstuyqjuopurtxowtcqrwwptrcttycopruwytwykolmwwywytorttcotxwulylyyucccwktywtcusuusujtuouuoyqujmktwpctcutttrwttwwwwmtcouwkstlkpyuqswyylrqwyuutyowckwwstutylcquutyuwtxoprytuwotkjwlyumslwktloxujtqwyjuycuytmwymlturwwtwtsmtpxpuwwwyttwmwoocrllcsyuoctyojwpktwywutusutjuruwouqouwtlrpuywtuwrwkwoocswotoujpuuoytxpyytmyutwwcwjutoqtrutjwypojtuxutctutwjsotojtwytwywworkwlrtxuttwuotyplumumuuruytutytlwrwysytmtlykwktywpyutxwlyuqoxkywtscumulwmxpwcqcjpmwuctxojytkxwqyrwrtumuswuttmuccoyktxttstrtukcktwyqxwqcluwyyyuuxtwucxtkcpotqooptwwowymtlmyytkcwyyttsxtolruutpotupttojtwkwrqslopqpotwtwrtowwwukopslopskowqymywwmsulttcllsuwmryjyktupstjmwukukwyupttoccttutwycwwyjutkqpuqrowukcspyuuxkwskwyukwukcjuuucupuwwxtwuopwlottutmwokttktxpjwomtqyutllrylrywyroytstcoslpyrwolwtwswwqwkwxxowtopqjttoxtwwupxxwoctyukompjjpscykkxpxwtwusmrouywtlkwumcjwtwywwtctpwlxkqjjjyltuomwtlpuotqurpsupwukwotlujtpuuucosmccttxwwqoottxwkqkjlwylpopxljwytuqwtwttstptocyoxtucwwttxwmowmwtluwykoyytqyorupowpskwyqwykuytuokjtkwptupjyruxwwcosttstjqjwwokswwywucpxwtycuyysqtrcxrurxwtcottxclwkyttoruqttlwcwuwtwxwyutyrtwuuwouxcucwostptutrwysxuwwscywwwttwtrjwmwtkwrlmykrwjprwytwyoywwrtyuykytmwwwyytwcrorttojuywttyotwyulsouuummywpsxlstkouptwrkutywtyoutktwuyptjwcptpowtucwjcooulsttturuowmpscwtptqwsxspwyrujotcwsokwwwtmrtkysyulorklyxylwcowuwourwtqtcukwooujttqwtykprltwxsjmlllujstomwmpwwtjwmmtqwwpjcotlwtrojcwkukcytuwwwwotkwtwytswtpokmcwmytuwwjtocjusjuwktxoktmtxwkostywqujowroottwoucwuuowulwjytylqwswjocltytuwmktytycuuuwmyuusltttpqlwrwwttcksjmxowtoqctckrkcuypooctlwrsqpruwumuruyouxmltqwstummtutsucmwuroumwmomwoxwluuruotuswxoytuyusjlwkyxuuwtpyyqtsyourkwoutwtyocrtytwslyxwucttoqtxyyltwlwyyyyyyttqtojtktptwqyjwmjlslyupltttspwcmtkorrtpwsrwtwwtcysqotycptuyuqutyukmkuujwujkywqowxuwuuoxquymyquywpwotluwktowswoyoujusukloyoywyjurwltjtwutktwqwrqrwtqmwxwtksrytoojrookuytttlsqwuptt


#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cassert>

using namespace std;
const int CHARMAX=26;

bool incl(int* stat, int* remain) {
    for(int i=0 ; i<CHARMAX; i++)
        if(stat[i] > remain[i])
            return false;
    return true;
}

int nextidx(string &s, int idx, int* stat, int* remain) {
    int smallidx = idx;
    int tmpremain[CHARMAX];
    for(int j=0; j<CHARMAX; j++) tmpremain[j]= remain[j];
    
    for(int i=idx; i<s.size(); i++) {
        if(stat[s[i]-'a'] > 0 && s[i]<s[smallidx]) {
            if(incl(stat, tmpremain)) {
                smallidx = i;
            }
        }
        tmpremain[s[i]-'a']--;
    }
    return smallidx;
}

int main() {
    string s;
    cin >> s;
    int stat[CHARMAX], remain[CHARMAX];
    for(int i=0; i<CHARMAX; i++)
        stat[i] = 0;
    for(int i=0; i<s.size(); i++)
        stat[s[i]-'a']++;
    for(int i=0; i<CHARMAX; i++) {
        remain[i] = stat[i];
        stat[i] /= 2;
    }
    
    string ans;
    for(int i=0; i<s.length(); i++) {
        int ni = nextidx(s, i, stat, remain);
        char thechar = s[ni];
        if(stat[thechar-'a']-- > 0) ans += thechar;
        if(ans.size() == s.length()/2) break;
        
        for(int j=i; j<=ni; j++)
            remain[s[j]-'a']--;
        i = ni;
    }
    cout << ans << endl;
    return 0;
}