Statistics

Problem Statement for "SubstringReversal2"

Problem Statement

You are given a string S of length N. Consider an even-sized subset of {1, 2,..., N}. Say the subset is { p1, p2,.., p2k} such that p1 < p2 < ... < p2k. Now we'll construct a new string from S as follows : reverse the substring from p(2i-1) to p(2i) (inclusive) for each i from 1 to k. Now consider the multiset of strings which can be built in this method by choosing all even-sized subset of {1, 2,..., N}. You have to find the Kth lexicographical string that can be built. It is guaranteed that such a string exists.

Say N = 8, and let's choose a subset, say {1, 3, 6, 8}. Then we reverse the substrings S[1 : 3] and S[6 : 8]. (1-based indexing)


For example, for the string "abcd", the following strings can be built :
abcd
abdc
acbd
adcb
bacd
badc
cbad
dcba
The 3rd lexicographical string is acbd.

Definition

Class:
SubstringReversal2
Method:
solve
Parameters:
String, long
Returns:
String
Method signature:
String solve(String S, long K)
(be sure your method is public)

Notes

  • Given two strings A and B of equal length, we say that A is lexicographically smaller than B if A has a smaller character than B at the first position where they differ.
  • It's guaranteed that such a string will exist.

Constraints

  • S will contain between 1 and 200 elements, 'a'-'z'.
  • K will be between 1 and 1018.

Examples

  1. "abcd"

    6

    Returns: "badc"

    For the string "abcd", the strings generated are "abcd", "abdc", "acbd", "adcb", "bacd", "badc", "cbad" and "dcba". Among them the 6th lexicographic string is "badc".

  2. "topcoder"

    40

    Returns: "otpdocre"

  3. "jivfdgznwj"

    116

    Returns: "ijvdfgjwnz"

  4. "jycirusfrekgpbu"

    15994

    Returns: "yjricusrfkeubpg"

  5. "omasiyswsbsweyascjytiymav"

    8753020

    Returns: "oamyissswwsbayesjctyimyav"

  6. "wowynpwubbfwokkawyjkgdyqsrcvvpomgovjzahw"

    460341033182

    Returns: "wwoynwpubfbkowkjywadgkqysrcvpvomvogjwhaz"

  7. "aeaielurcbpakvflwjodfnoxnphsclnbjgrqquwsvrjgdqdtddcvfeayrdmlmgnszldddy"

    309743358464505200

    Returns: "aaebcruleikapdojwlfvnfxohpncslnjbgqrquswrvjdtdqdgvcdyaeflmdrmngslzdydd"

  8. "qgxkzenizfoybvyjhoovmprdytuqekriprktukeskkadrzodyktkcqovmlnjqeipsyquqtomqzmniubncqtgkjdetnryeflvjigy"

    770197026888471724

    Returns: "byofzinezkxgqdrpmvoohjyvekutkrpirkequtykskozrdadycktkqvolmjnqeipqystquqmoznmitqcnbukgjdtenfeyrvlijgy"

  9. "dzrscpasdrwlgyudaayshduyxmlqnjmxpblglbetmepmdvnwiojjuekszuyebyztrqumiszmorjjmvlfaxgdcuvtnopuipsevoqzwgjmytiaaxeeumpgkbryklzxlzfnwepdktnoxcdcvjmuuewaiyoxqgtjlgomayytaupfxkyscjilrfaczwhyehwzjxvoftpkpzgp"

    1000000000000000000

    Returns: "aaduyglwrdsapcsrzdaaitymjgwzqovespiupontvucdgxaflvmjjromzsimuqrtzybeyuzskeujjoiwnvdmpemteblglbpxmjnqlmxyudhsybkgpmueexcxontkdpewnfzlxzlkyrcdvjuumaweiqxoytgjoglyamytapufxykfrlijcsaczwhywhezjovxftkppzpg"

  10. "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz"

    1000000000000000000

    Returns: "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz"

  11. "eelkzqznkvhfwgjtuanmmidnukaabdqgqrxajxogpmdugulgrvzxkydnrpqhyudcwccwtueebogkwqwssuypkrknamxnbcpsmlcnzpzqdvvcumrozwgekvlmysqddlocrwnmqzyskalvhngsplihfnrokrmxqihfsawxnnelfmjjslcmvdodtikjbaxsytwhxouqkpnr"

    628172560533937340

    Returns: "aakundimmnautjgwfhvknzqzkleeaksyzqmnwrcolddqsymlvkegwzormucvvdqzpznclmspcbnxmankrkpyusswqwkgobeeutwccwcduyhqprndykxzvrglugudmpgoxjaxrqgqdblhvnpsgilhfnrxmrkoqhifxwasnneflmjjslcmvdodkitxabjsyhwtpkquoxnr"

  12. "tpygufofghozvfeqkkguozkjuupamktrxnijxxiwxoeyxyysxbreslbismftzjavbadtwajryiqlgjtbnejvnjkvhxofvpplkzwjqclueszwsuhjrpgauapbvyjsxgjqcsvivbhaofpupcozbftddwxodqtoelufwmujcmroyispzjsgwqvmczglofclfmjowuxvwgtv"

    219366741526117660

    Returns: "abvajztfmsiblserbxsyyxyeoxwixxjinxrtkmapuujkzougkkqefvzohgfofugyptagprjhuswzseulcqjwzklppvfoxhvkjnvjenbtjglqiyrjawtdahbvivscqjgxsjyvbpaufocpupfbzotddwxqdoeotlwfumcjuyormispzgsjqwvcmlgzcfolfuwojmvxwgtv"

  13. "qgydwtehlpnujyzfmmhgrxdzegdoviygmxoodyaftasilzezbapgjjahhdtepjnnydlretxnnwmiicgoavxihrfmygqtaqtmnexzvbyjaunktzteqbdwwcbxebotuxdacwjcfeevrrroedsnkbkelpbtewcgwijlcilerfhxwsnmhtziucvoliebmvdmverprkimfzeh"

    399503712798070516

    Returns: "abzezlisatfaydooxmgyivodgezdxrghmmfzyjunplhetwdygqadxutobexbcwwdbqetztknuajybvzxenmtqatqgymfrhixvaogciimwnnxterldynnjpetdhhajjgpccjweefeorrrvdnskekbplbwgcwetiljclifreswxhcuizthmnovilmbevvmderprikmfzeh"

  14. "ywoubmvaielmbzfbsymqqkyaiahfveykirrflcxnfuxmlhyqkouukwgqxbiyvhainzlofkevhzqzyvmniqpavtwwmrxgiyuqcwqrjdzjhllpdcxiedldmshedlkwhiykxfwzfnoehqzaohzkzsmsajhitgjjuhjkafgyxvsrmuwrbnmfafcdynoournhkexvopfbosah"

    59739115590111413

    Returns: "ahvyibxqgwkuuokqyhlmxufnxclfrrikyevfhaiaykqqmysbfzbmleiavmbuowyapqinmvyzqzhvekfolzniazqheonfzwfxkyihwkldehsmdldeixcdpllhjzdjrqwcquyigxrmwwtvhozkasmszjjgtihjjhukfaygxmrsvwurfmnbcfadnyoounrkhexvofpbosah"

  15. "eemkzyqbjypddlonnhgkdzdplcrirrgkkxednsbusbhsalvlrxrrbzzdtuirnoxeeajpzuzkshfheyoiaoqtksqnrpeajmodcqqltqbspjhsfdpecoigrqmmkrzkcglgtlujlblyctztaycmntrbuyudesamwchecfzruwjiozhxeaofwzzgctqidqpqnoopfvuecrur"

    730152292958725155

    Returns: "aeexonriutdzzbrrxrlvlashbsubsndexkkgrrirclpdzdkghnnolddpyjbqyzkmeeaeprnqsktqoaioyehfhskzuzpjbljultglgckzrkmmqrgiocepdfshjpsbqtlqqcdomjcylatztmcynduyubrtasemwcheczfoijwurzhfoaexwzgzqtcidqonqppovfrurceu"

  16. "ywbjmxutjnvqvkjsmrtxstreuwdjtxcevahujhvbfuugiwlggknuucqnaixreldcjiymkoftwnhwbpxkvngyhgkxkikchpwbtksapobcsydrwquvkukzyhoucjejsjftmytrfhsikqhpdczfujcuarkkelwnwcrbcnrlbhjmcdrnrdzmuahvclsykirmhvujhohdcdfu"

    956321244872117950

    Returns: "anqcuunkgglwiguufbvhjuhavecxtjdwuertsxtrmsjkvqvnjtuxmjbwyasktbwphckikxkghygnvkxpbwhnwtfokmyijcdlerxibopccuohyzkukvuqwrdysejdphqkishfrtymtfjsjzcaucjufkrkwnwlebrcrncbljhmrdcrndzumahlcvsyrikmhvuhjhofdcdu"

  17. "aabc"

    2

    Returns: "aabc"

    For the string "aabc", the strings generated are "aabc", "aabc", "aacb", "aacb", "abac", "acba", "baac" and "cbaa". Among them the 2nd lexicographic string is "aabc".

  18. "ajshcdsfbekjndkjsdjksbkjdbfkjdkjdvkdbvhkjhdvjkdyetdkfkfjndklfjkfjgnjkfngjkfnjkngjknfjkvgnfkjgnjkfngkjrn"

    100000000000

    Returns: "abdjkbskjdsjkdnjkebfsdchsjbdkvdjkdjkfdhjkhvdkjvdnjfkfkdteyfkjflkjgjnnfkgjfkjnnkgjnkkjfgvnkfjjngnfkjkgrn"

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: