Problem Statement
- The number of inversions in R is at least minInv.
- The string R is not lexicographically smaller than minStr.
Definition
- Class:
- StrIIRec
- Method:
- recovstr
- Parameters:
- int, int, String
- Returns:
- String
- Method signature:
- String recovstr(int n, int minInv, String minStr)
- (be sure your method is public)
Notes
- A String A is lexicographically smaller than a String B if A is a prefix of B or A contains a smaller character at the first position where the Strings differ.
Constraints
- n will be between 1 and 20, inclusive.
- minInv will be between 0 and n*(n-1)/2, inclusive.
- minStr will contain between 1 and n characters, inclusive.
- Each character in minStr will be one of the first n lowercase Latin letters.
- All characters in minStr will be unique.
Examples
1
0
"a"
Returns: "a"
2
0
"a"
Returns: "ab"
2
0
"b"
Returns: "ba"
2
1
"a"
Returns: "ba"
2
1
"b"
Returns: "ba"
2
0
"ab"
Returns: "ab"
2
1
"ab"
Returns: "ba"
You must find the lexicographically smallest String that has at least 1 inversion and is not lexicographically smaller than "ab".
2
0
"ba"
Returns: "ba"
2
1
"ba"
Returns: "ba"
16
64
"k"
Returns: "kabcdopnmljihgfe"
9
1
"efcdgab"
Returns: "efcdgabhi"
13
77
"ljhefmciabdgk"
Returns: "lmkjihgfedcba"
3
0
"bca"
Returns: "bca"
8
1
"gdbcah"
Returns: "gdbcahef"
15
3
"enjkmlbhaio"
Returns: "enjkmlbhaiocdfg"
11
12
"acgedif"
Returns: "acgedifbhjk"
8
16
"af"
Returns: "afdhgecb"
13
33
"dkmlabfghj"
Returns: "dkmlabfghjcei"
10
12
"hdfjig"
Returns: "hdfjigabce"
11
16
"dhiajge"
Returns: "dhiajgebcfk"
4
1
"ca"
Returns: "cabd"
3
0
"acb"
Returns: "acb"
3
1
"c"
Returns: "cab"
13
32
"fcdbh"
Returns: "fcdbhakmljige"
18
84
"ifebqhljk"
Returns: "ifebqhljkrponmgdca"
20
124
"rosqkcip"
Returns: "rosqkcipabdjtnmlhgfe"
15
105
"jkblogm"
Returns: "onmlkjihgfedcba"
11
0
"egifh"
Returns: "egifhabcdjk"
3
0
"bac"
Returns: "bac"
11
55
"debgikjfc"
Returns: "kjihgfedcba"
"kjihgfedcba" is the only String that has at least 55 inversions.
4
4
"cbd"
Returns: "cbda"
11
2
"fhgkicb"
Returns: "fhgkicbadej"
18
51
"hqkrebo"
Returns: "hqkreboacdfgijlmnp"
13
65
"fcedmjigl"
Returns: "fgmlkjihedcba"
18
136
"o"
Returns: "ocrqpnmlkjihgfedba"
11
4
"biaf"
Returns: "biafcdeghjk"
4
4
"ad"
Returns: "bdca"
9
10
"b"
Returns: "bacdhigfe"
4
5
"ad"
Returns: "cdba"
5
1
"e"
Returns: "eabcd"
20
99
"asjilotdqgcepbmnkrh"
Returns: "asjilotdqgcepbmnrkhf"
12
39
"labdefcgkhij"
Returns: "labdjkihgfec"
8
14
"h"
Returns: "habdgfec"
19
122
"afqinebcsrmlgh"
Returns: "afqinosrpmlkjhgedcb"
6
12
"bfead"
Returns: "cfedba"
6
7
"bcd"
Returns: "bcefda"
17
16
"e"
Returns: "eabcdfghijknqpoml"
4
1
"cbd"
Returns: "cbda"
10
27
"aihecjgf"
Returns: "aihecjgfdb"
8
22
"fahb"
Returns: "fchgedba"
15
24
"adilgme"
Returns: "adilgmebcfhjkno"
14
72
"fcengdika"
Returns: "fcmnlkjihgedba"
12
50
"gjeh"
Returns: "gjehklifdcba"
19
116
"enhmdirfbjlosk"
Returns: "enhmdirqspolkjgfcba"
7
6
"bfd"
Returns: "bfdaceg"
9
20
"feh"
Returns: "fehabigdc"
6
12
"dcbfe"
Returns: "defcba"
20
39
"mahkidsbtpref"
Returns: "mahkidsbtprefcgjlnoq"
8
18
"defhac"
Returns: "defhcgba"
16
15
"ahjpk"
Returns: "ahjpkbcdefgilmno"
18
124
"bqkdrflcinej"
Returns: "bqkjrponmlihgfedca"
9
17
"hcedfbai"
Returns: "hcedfbaig"
8
28
"gabhdcf"
Returns: "hgfedcba"
20
24
"lfd"
Returns: "lfdabceghijkmnopstrq"
17
69
"apqemchbldkgi"
Returns: "apqemchbldkjonigf"
5
4
"a"
Returns: "acedb"
6
11
"f"
Returns: "faedcb"
19
24
"enbosmr"
Returns: "enbosmracdfghijklpq"
5
1
"ebac"
Returns: "ebacd"
17
88
"lipbn"
Returns: "lipbnacqomkjhgfed"
13
48
"jlhaci"
Returns: "jlhacidmkgfeb"
6
11
"abc"
Returns: "bfedca"
8
13
"gcbhde"
Returns: "gcbhdeaf"
19
19
"ebjcha"
Returns: "ebjchadfgiklmnoprsq"
19
48
"caro"
Returns: "carobdefghijpsqnmlk"
11
6
"cakib"
Returns: "cakibdefghj"
18
42
"fpbkojqgenrilhdac"
Returns: "fpbkojqgenrilhdacm"
11
2
"edbjaki"
Returns: "edbjakicfgh"
8
10
"e"
Returns: "eabchgfd"
9
21
"h"
Returns: "habgifedc"
8
16
"cfh"
Returns: "cfhaegdb"
14
56
"kiamjhbecld"
Returns: "kiamjhbelngfdc"
19
18
"irfebmslhgadn"
Returns: "irfebmslhgadncjkopq"
10
18
"aie"
Returns: "aiebcgjhfd"
11
43
"hejgb"
Returns: "hejgikfdcba"
15
22
"glmc"
Returns: "glmcabdefhijkno"
4
3
"adcb"
Returns: "adcb"
20
41
"cardgepnlbhsfk"
Returns: "cardgepnlbhsfkijmoqt"
15
70
"onfmcj"
Returns: "onfmcjabhlkiged"
9
29
"fadg"
Returns: "fdihgecba"
9
5
"igehacbd"
Returns: "igehacbdf"
10
37
"cjfbegad"
Returns: "cjhigfedba"
13
40
"cbfmkjadielh"
Returns: "cbfmkjaglihed"
13
29
"fmcbkaigjeld"
Returns: "fmcbkaigjeldh"
19
134
"fshkpinjemqdoblagr"
Returns: "fshkplrqonmjigedcba"
15
0
"e"
Returns: "eabcdfghijklmno"
7
20
"d"
Returns: "fgedcba"
18
48
"nbchflikdr"
Returns: "nbchflikdraegjmopq"
9
20
"fcdebiha"
Returns: "fcdehigba"
6
2
"bfad"
Returns: "bfadce"
9
19
"ecah"
Returns: "ecahgifdb"
12
41
"hbgdj"
Returns: "hbgdjlkifeca"
12
38
"a"
Returns: "abelkjihgfdc"
20
148
"ogrhsf"
Returns: "ogrhsfntqpmlkjiedcba"
12
29
"gkc"
Returns: "gkcabdhljife"
18
19
"eqncbkoflrhjma"
Returns: "eqncbkoflrhjmadgip"
15
82
"ne"
Returns: "neamolkjihgfdcb"
9
1
"cahfgbei"
Returns: "cahfgbeid"
15
61
"jmkhnd"
Returns: "jmkhndabciolgfe"
20
17
"cijnsqbephkatfdroglm"
Returns: "cijnsqbephkatfdroglm"
20
79
"phjn"
Returns: "phjnabcdefktsrqomlig"
20
5
"bedo"
Returns: "bedoacfghijklmnpqrst"
20
189
"mikjardhcnltfqo"
Returns: "strqponmlkjihgfedcba"
20
0
"eljtohsbkfid"
Returns: "eljtohsbkfidacgmnpqr"
20
190
"mj"
Returns: "tsrqponmlkjihgfedcba"
20
156
"pfjmqkdarlegthscobin"
Returns: "pfjmrtsqonlkihgedcba"
20
30
"mnglorcifpbethjkdqas"
Returns: "mnglorcifpbethjkdqas"
20
93
"r"
Returns: "rabcdefqtsponmlkjihg"
20
0
"q"
Returns: "qabcdefghijklmnoprst"
20
0
"mq"
Returns: "mqabcdefghijklnoprst"
20
184
"filhtmkeajpobqdscgrn"
Returns: "ntsrqpomlkjihgfedcba"
20
187
"c"
Returns: "qtsrponmlkjihgfedcba"
20
1
"jicndftlobmhqapgsrke"
Returns: "jicndftlobmhqapgsrke"
20
187
"jasghodbcmreqflin"
Returns: "qtsrponmlkjihgfedcba"
20
188
"gnha"
Returns: "rtsqponmlkjihgfedcba"
20
188
"ckamtdrfblhqnipeojgs"
Returns: "rtsqponmlkjihgfedcba"
20
84
"k"
Returns: "kabcdefptsrqonmljihg"
20
0
"itfhaqsbodlkjn"
Returns: "itfhaqsbodlkjncegmpr"
20
185
"kcplegqo"
Returns: "otsrqpnmlkjihgfedcba"
20
0
"rnsdjfibgclphemqaok"
Returns: "rnsdjfibgclphemqaokt"
20
6
"c"
Returns: "cabdefghijklmnoprtsq"
20
173
"oncijgrmhakbedts"
Returns: "onktsrqpmljihgfedcba"
20
3
"qrslchogjbdnetfkaim"
Returns: "qrslchogjbdnetfkaimp"
20
62
"agb"
Returns: "agbcdefhktsrqponmlji"
20
5
"bkodjecamhqgrtfnpis"
Returns: "bkodjecamhqgrtfnpisl"
20
79
"rhdictqojapmkl"
Returns: "rhdictqojapmklbefgns"
20
180
"aomtgrknslecfibqjdhp"
Returns: "jtsrqponmlkihgfedcba"
20
42
"ih"
Returns: "ihabcdefgjklstrqponm"
20
190
"nbdqchgltakjipemfr"
Returns: "tsrqponmlkjihgfedcba"
20
189
"scgkbqnejptfldrmhi"
Returns: "strqponmlkjihgfedcba"
20
175
"sjcnitagrqfkbelphmd"
Returns: "sjntrqpomlkihgfedcba"
20
8
"jcibomhegpd"
Returns: "jcibomhegpdafklnqrst"
20
185
"trc"
Returns: "trnsqpomlkjihgfedcba"
20
190
"dp"
Returns: "tsrqponmlkjihgfedcba"
20
141
"jd"
Returns: "jdamtsrqponlkihgfecb"
20
1
"ltgskpobhmfd"
Returns: "ltgskpobhmfdaceijnqr"
20
179
"hkmldcgfpiobt"
Returns: "itsrqponmlkjhgfedcba"
20
1
"stmopcl"
Returns: "stmopclabdefghijknqr"
20
2
"idctqmfonbkjresp"
Returns: "idctqmfonbkjrespaghl"
20
0
"fjpmldbcniqshkgoear"
Returns: "fjpmldbcniqshkgoeart"
20
5
"lcoerk"
Returns: "lcoerkabdfghijmnpqst"
20
187
"tdjsingplohmea"
Returns: "tpsrqonmlkjihgfedcba"
20
188
"fsheicnod"
Returns: "rtsqponmlkjihgfedcba"
20
0
"tgm"
Returns: "tgmabcdefhijklnopqrs"
20
150
"brsmfhjkg"
Returns: "brsmfotqpnlkjihgedca"
20
1
"dnarhjlm"
Returns: "dnarhjlmbcefgikopqst"
20
190
"dcaqkr"
Returns: "tsrqponmlkjihgfedcba"
20
7
"p"
Returns: "pabcdefghijklmnoqrst"
20
187
"klgrcpjobnmqdea"
Returns: "qtsrponmlkjihgfedcba"
20
185
"ajsdflk"
Returns: "otsrqpnmlkjihgfedcba"
20
123
"k"
Returns: "kabcmtsrqponljihgfed"
20
190
"a"
Returns: "tsrqponmlkjihgfedcba"
20
70
"abdej"
Returns: "abdejcfgqtsrponmlkih"
20
100
"a"
Returns: "abcdeotsrqpnmlkjihgf"
20
20
"a"
Returns: "abcdefghijklmstrqpon"
11
55
"kjihgfedcba"
Returns: "kjihgfedcba"
20
130
"a"
Returns: "abcntsrqpomlkjihgfed"
20
31
"abcdqefghijklmnop"
Returns: "abcdqefghijklrtsponm"
12
56
"debgikjfcl"
Returns: "djlkihgfecba"
20
34
"abcdefghi"
Returns: "abcdefghijkrtsqponml"
20
180
"abcdmnopqrstefghijkl"
Returns: "jtsrqponmlkihgfedcba"
20
176
"tip"
Returns: "tiprsqonmlkjhgfedcba"
20
179
"mbjcalhtepsfonkqgdir"
Returns: "mptsrqonlkjihgfedcba"
20
190
"abcdefghijklmnopqrst"
Returns: "tsrqponmlkjihgfedcba"
20
150
"abcdefghijklmnopqrst"
Returns: "abqtsrponmlkjihgfedc"
20
100
"dcaefog"
Returns: "dcaefoltsrqpnmkjihgb"
20
100
"abcdefg"
Returns: "abcdeotsrqpnmlkjihgf"
20
130
"tqcd"
Returns: "tqcdabsrponmlkjihgfe"
20
171
"a"
Returns: "atsrqponmlkjihgfedcb"
20
190
"abcdehjkmnpoqrstf"
Returns: "tsrqponmlkjihgfedcba"
15
0
"abcdefghijklmno"
Returns: "abcdefghijklmno"
20
189
"onm"
Returns: "strqponmlkjihgfedcba"
20
3
"a"
Returns: "abcdefghijklmnopqtsr"
20
190
"s"
Returns: "tsrqponmlkjihgfedcba"
20
190
"tsrqponmlkjihgfedcba"
Returns: "tsrqponmlkjihgfedcba"
5
3
"abdec"
Returns: "abedc"
19
20
"fcdebihamnk"
Returns: "fcdebihamnkgjlopqrs"
20
90
"a"
Returns: "abcdefstrqponmlkjihg"
20
95
"a"
Returns: "abcdejtsrqponmlkihgf"
20
190
"bacdefghijklmnopqrst"
Returns: "tsrqponmlkjihgfedcba"
4
3
"abcd"
Returns: "adcb"
3
0
"abc"
Returns: "abc"
20
50
"a"
Returns: "abcdefghiotsrqpnmlkj"
20
190
"abcdefghijklmnop"
Returns: "tsrqponmlkjihgfedcba"
3
1
"bac"
Returns: "bac"
15
88
"nbcdefghklmo"
Returns: "nbjomlkihgfedca"
19
20
"fcdebiha"
Returns: "fcdebihagjklmnopsrq"
4
3
"a"
Returns: "adcb"
9
10
"fcdebiha"
Returns: "fcdebihag"
16
50
"ib"
Returns: "ibacdelponmkjhgf"
6
8
"a"
Returns: "adfecb"
19
151
"b"
Returns: "bpsrqonmlkjihgfedca"
20
66
"abcdefghijklmnopqrst"
Returns: "abcdefghtsrqponmlkji"
20
171
"bacdefghijklmnopqrst"
Returns: "bstrqponmlkjihgfedca"
20
180
"a"
Returns: "jtsrqponmlkihgfedcba"
20
129
"a"
Returns: "abcmtsrqponlkjihgfed"