Problem Statement
String C is obtained by shuffling strings A and B if we can create C by repeatedly taking either the first character of A or the first character of B. Formally, string C is obtained by shuffling strings A and B if length(C) = length(A) + length(B) and there are sequences of integers X and Y such that:
- length(X) = length(A) and length(Y) = length(B).
- For each valid i, X[i] < X[i+1].
- For each valid i, Y[i] < Y[i+1].
- For each valid i and j, X[i] != Y[j].
- For each valid i, C[X[i]] = A[i].
- For each valid i, C[Y[i]] = B[i].
Replace each '?' with a letter in such a way that the resulting string S can be obtained by shuffling A and B. Return the resulting string S. If there are multiple solutions, return the lexicographically smallest one. If there is no solution, return an empty
Definition
- Class:
- MergeStrings
- Method:
- getmin
- Parameters:
- String, String, String
- Returns:
- String
- Method signature:
- String getmin(String S, String A, String B)
- (be sure your method is public)
Notes
- Given two distinct strings X and Y such that length(X)=length(Y), the lexicographically smaller one is the one that has a character with a smaller ASCII value on the first position on which they differ.
Constraints
- S will contain between 1 and 50 characters, inclusive.
- The number of characters in S will be same as the total number of characters of A and B.
- Each character in S will be an uppercase letter ('A'-'Z') or '?'.
- Each character in A and B will be an uppercase letter ('A'-'Z').
Examples
"??CC??"
"ABC"
"BCC"
Returns: "ABCCBC"
Out of all strings that can be obtained by shuffling "ABC" and "BCC", only two match "??CC??": the strings "ABCCBC" and "BACCBC". The string "ABCCBC" is the lexicographically smaller of the two.
"WHAT?"
"THE"
"WA"
Returns: ""
None of the strings obtained by shuffling "THE" and "WA" matches "WHAT?".
"PARROT"
"PARROT"
""
Returns: "PARROT"
One of A and B may sometimes be empty.
"???????????"
"AZZAA"
"AZAZZA"
Returns: "AAZAZZAAZZA"
"?"
""
"X"
Returns: "X"
"??????????????????????????????????????????????????"
"AAAAAAAAAAAAAAAAAAAAAAAAA"
"AAAAAAAAAAAAAAAAAAAAAAAAA"
Returns: "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
"Q"
"Q"
""
Returns: "Q"
"???"
"ZZX"
""
Returns: "ZZX"
"??S?A"
"A"
"WSLA"
Returns: "AWSLA"
"?L???T?"
"TLTERTC"
""
Returns: "TLTERTC"
"W????WVU?"
"WKXAWVUX"
"O"
Returns: "WKOXAWVUX"
"???????????"
"JIVTEXSV"
"LZL"
Returns: "JILVTEXSVZL"
"?????????????"
"AEQIPD"
"UIVDSRM"
Returns: "AEQIPDUIVDSRM"
"????Q???J???B?X"
"PIQJBQ"
"CPVJVXBLX"
Returns: "CPIPQJBVJQVXBLX"
"?????????????????"
"XEDTTEQZWTJ"
"BOIWTV"
Returns: "BOIWTVXEDTTEQZWTJ"
"?????????X???????I?"
"OOIIQWFDKSOD"
"OXXQLIV"
Returns: "OOIIOQWFDXKSODXQLIV"
"?????????P????????A??"
"M"
"VQDVMTPFPCQXNXXLRANL"
Returns: "MVQDVMTPFPCQXNXXLRANL"
"???????V?WV?O?W???V?W??"
"OWOVOOOVOWVWOWWVWWVW"
"OOW"
Returns: "OWOVOOOVOWVOOWWOWWVWWVW"
"WYTDYPFYWTBTCBWQIDFZLLWFW"
"WYTDYPFYWTBTCBWQIDFZLL"
"WFW"
Returns: "WYTDYPFYWTBTCBWQIDFZLLWFW"
"BSBREXDEXBVXWVBXVBEDWCWSZWX"
"BSREEXVWVB"
"BXDBXXVBEDWCWSZWX"
Returns: "BSBREXDEXBVXWVBXVBEDWCWSZWX"
"????V?V???????????V?V??????V?"
"VVVVVVVVVVVVVVVVVV"
"VVVVVVVVVVV"
Returns: "VVVVVVVVVVVVVVVVVVVVVVVVVVVVV"
"????????VX?????????????????T???"
"FPP"
"TKDYGVXTPPBCBYTNGGPGPPFMTPAG"
Returns: "FPPTKDYGVXTPPBCBYTNGGPGPPFMTPAG"
"???O?A???D???F??????????X?R?UU???"
"GF"
"NOUANURDQUFFNUJFXXTGHEXYROUUOMG"
Returns: "GFNOUANURDQUFFNUJFXXTGHEXYROUUOMG"
"USXMBWUBGPUGFVSXUXUUGMMPFBSWMSGXUVG"
"USXMBWUBGPUGFVSXUXUUGMMPFBSWMSGXU"
"VG"
Returns: "USXMBWUBGPUGFVSXUXUUGMMPFBSWMSGXUVG"
"?L???????????C?D??????????????Y??????"
"ELQTAOBAATCCADKDZWI"
"ASJZBSOVIHFYMQKEWH"
Returns: "ELAQSTAOBAATCCADJKDZBSOVIHFZWIYMQKEWH"
"?RZZ??T?WVSB?????BNY???A?YY??B?NRT?BSR?"
"RZZRG"
"TTFWVSBPZBWIBNYICGAYYYSWBVNRTCBSRC"
Returns: "TRZZRGTFWVSBPZBWIBNYICGAYYYSWBVNRTCBSRC"
"T?????????TRE????????R??R??R????RH?????LE"
"RZRNN"
"TEHLTTREHNELELNTRTRRTLRNEELRHLLZLTLE"
Returns: "TEHLRTZRNNTREHNELELNTRTRRTLRNEELRHLLZLTLE"
"VSZWAYUFJYIEUUJCFHQQQJQYBYPEHHTSEBNMUKHXHCP"
"VSZWAYUF"
"JYIEUUJCFHQQQJQYBYPEHHTSEBNMUKHXHCP"
Returns: "VSZWAYUFJYIEUUJCFHQQQJQYBYPEHHTSEBNMUKHXHCP"
"C??C?C??C?CCC?????CCC???CC???C?CCCCCC?CC??CC?"
"CCCCCCCCCCCCC"
"CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC"
Returns: "CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC"
"??R????LL??G???S??GG??G?R??????????R???G??????G"
"LRRSLLSGLGRSSLG"
"LLSLGRRGURSGGSRUULLURUUUGLUSLLSG"
Returns: "LLRLRSSLLLSGLGRSSLGGRRGURSGGSRUULLURUUUGLUSLLSG"
"I?????FL????????????????A????X???????????????????"
"IEFKKFLPITHVHKWTGIPWKAGVPFXZQVAVGQZZGAEGXKAZTH"
"XXV"
Returns: "IEFKKXFLPITHVHKWTGIPWKXVAGVPFXZQVAVGQZZGAEGXKAZTH"
"?????????????????G???H???UC??PU?N?C???????????????"
"NYPXCXCXUPHHGHUUHGUPUCYPPUNNPCHCGXNCHHPPYYPNU"
"CXGXY"
Returns: "CNXGXYPXCXCXUPHHYGHUUHGUPUCYPPUNNPCHCGXNCHHPPYYPNU"
"?QZ??????????????????????C????????W???U????E???AY?"
"QZQXLUALBARDUOHQZLMHXUOXCELXWLYONWRFLULZGIEAGIAYW"
"I"
Returns: "IQZQXLUALBARDUOHQZLMHXUOXCELXWLYONWRFLULZGIEAGIAYW"
"CHFKTCHHNCFNLKBNFCLFLKTFNFBLHKKBCLNFKTCNTOBNHCCKLT"
"CHFK"
"TCHHNCFNLKBNFCLFLKTFNFBLHKKBCLNFKTCNTOBNHCCKLT"
Returns: "CHFKTCHHNCFNLKBNFCLFLKTFNFBLHKKBCLNFKTCNTOBNHCCKLT"
"??L?B????L???V?Z?K?????LB??N????B???????L?B????L?E"
"LEBVNLL"
"NBBBEEVLZLKVKBLZLBVZNNZNZBVKVKEBZLKBLLBNLZE"
Returns: "NBLBBEBVNLEELVLZLKVKBLZLBVZNNZNZBVKVKEBZLKBLLBNLZE"
"?L??L?????IH??????????????M??????????T?????????QE?"
"DOORVEHLJRHD"
"LALKICYSPXOPUQMLPWVAKDYRHTECYATXNNLQEI"
Returns: "DLAOLKORVEIHCLJRHDYSPXOPUQMLPWVAKDYRHTECYATXNNLQEI"
"WWLB???ZHG?HMPI??P??OY?Q??CT?WZEVJ??????WBF?C?GJJ?"
"WWLBZSGZGNHMPIEXPCOYQWJCTSWEVJPNGNGWBOCBGJJ"
"HUMZTFI"
Returns: "WWLBZSGZHGNHMPIEXPCUOYMQWJCTSWZEVJPNGNGTWBFOCBGJJI"
"?????????????????????K?????????D?????????????????V"
"USIPJJFHHUADEEZCXMTFKTEYHTLIDLMIHYYZLQSVIKX"
"FFDTLKV"
Returns: "FUSIPJJFHHUADEEZCXMTFKFDTEYHTLIDLMIHTLKYYZLQSVIKXV"
"L???????S??O???????????L?D????????S?J?N???????????"
"LHTHBINJIDVNXNJIVLD"
"LSBOXZKTBJZBOHLSNJNNLVHPOHVOLID"
Returns: "LHLTHBINSBJOIDVNXNJIVXZLKDTBJZBOHLSNJNNLVHPOHVOLID"
"W?WW??????P??CC?????????????????????P?W????P?C???W"
"WWWCWWCPCWC"
"WPCCWWWCCCPWPWPWPWWWWCCPCPPWWWWPPCCWWWW"
Returns: "WPWWCWCWWCPCWCCWWWCCCPWPWPWPWWWWCCPCPPWWWWPPCCWWWW"
"?????S????????????????????S?S?S?????S???????S?????"
"SSSSSSSS"
"SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS"
Returns: "SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS"
"??K?????I??Q?ZM?DPM??????V?N??????H?P??V?E????????"
"ZKQVAIRNRMKPMCMSRPUVRNPPCYEYHHPCSVJEUZOILCEA"
"DMXQZD"
Returns: "DZKMQVAXIRNQRZMKDPMCMSRPUVRNPPCYEYHHPCSVJEUZOILCEA"
"EFGJFFKFO?K?EVKK?M?MJE???O?M????VO???E?OU?EMK?M???"
"EFGJFFKFEKUEKKOMOMJEVMUOMMMVG"
"OVVVOUEGEFOUOEMKGMGOK"
Returns: "EFGJFFKFOEKUEVKKOMOMJEVMUOMMMVGVVOUEGEFOUOEMKGMGOK"
"?????????????????????T?????X??J??H???????????B??R?"
"IOJTOXRRGRUJZOKITJYTSOTRLXIKJWIHHROSRXO"
"WJIGBKBXZRW"
Returns: "IOJTOWJXRRGRUJZOKITJYTSOTRLXIKJWIHHIGBKROSRXOBXZRW"
"FVVKGHDZDGEQOOLDDPLLTTFUHCPLVUTFHKZCPZCCVGUZDLKZNN"
"VVGHDZDGEQOOLDPLLTTFUHCPLVUTFHKZCPZCCVGUZDLKZNN"
"FKD"
Returns: "FVVKGHDZDGEQOOLDDPLLTTFUHCPLVUTFHKZCPZCCVGUZDLKZNN"
"?G???EU?O?Z???????GN????E?M??H?????E?????B?B?Q??JU"
"GOYOMOZLUWNSGNYJYECMEUDYHMZBCBVQUVJU"
"AEUVGAAZHZEUGQ"
Returns: "AGOYOEUMOVZGALUWNSGNAYJYECMEZHUDYHZEMUGQZBCBVQUVJU"
"???????H???T????????????????????????????????U?????"
"TVPETH"
"ZNGPUTXQKXHQZTWQUKNHHUTNNVUPZPNHXKNTVVUNWUZW"
Returns: "TVPETZNHGPUTXQKXHQZTWQUKNHHUTNNVUPZPNHXKNTVVUNWUZW"
"????K??????????????D???K???K????????K?????K???????"
"KKKKKDKKKDKKDDKDDDKDKK"
"KDKDDKKKDDKDDKKKDKDKKDDDDDDD"
Returns: "KDKDKDKKKDDKDDKKKDKDKKDKDDDKDDDKKDKKKDKKDDKDDDKDKK"
"KZRKRZZRRRKBRKKRKZKKBZBRRKBBZRKBKZRRRRRBKRBZRBBKKB"
"ZKRZRRKBKKRKKBZBRRBBZRK"
"KRZRRZKKBKZRRRRRBKRBZRBBKKB"
Returns: "KZRKRZZRRRKBRKKRKZKKBZBRRKBBZRKBKZRRRRRBKRBZRBBKKB"
"?P??W???????????E???R???????????????E?????????????"
"WPOEWWPEEEEROREEWORRPEROEOOROREREPWW"
"EPRPOWRPEEOPEO"
Returns: "EPRPWOPOEWRPEWWPEEEEREOOPREEWORRPEROEEOOOROREREPWW"
"??????????????????????????????????????????????????"
"BBCBJEBCCCJCEECCBCEEEJBEBJCJEEJEJJEJEJE"
"JBCJCCBEJJB"
Returns: "BBCBJBCJCCBEJEBCCCJCEECCBCEEEJBEBJCJEEJEJJBJJEJEJE"
"???VV??LXM?S????L?OXG?B?HHB?BBGL??B??B??V?B??Y????"
"OVVPOLXM"
"SYGSOVMBLGOXGEBYHHBGBBGLHGBGYBVEVLBOEYLGPX"
Returns: "OSYVVPOLXMGSOVMBLGOXGEBYHHBGBBGLHGBGYBVEVLBOEYLGPX"
"YQ????????????????S?S?S????????D??????????????Z?TU"
"QQEMTTNOL"
"YYLZSZMIYSNSNSYLYUZDINDMIOSLMNQZADODEZITU"
Returns: "YQQEMTTNOLYLZSZMIYSNSNSYLYUZDINDMIOSLMNQZADODEZITU"
"VPSXPXKKLXXNQNQRASNQAASRXXPQLARAXALRVAXRKRVPVALPSX"
"VPS"
"XPXKKLXXNQNQRASNQAASRXXPQLARAXALRVAXRKRVPVALPSX"
Returns: "VPSXPXKKLXXNQNQRASNQAASRXXPQLARAXALRVAXRKRVPVALPSX"
"H?HVZ?WW???T??H??V??????G?W?D?????D????G?T????V??G"
"HXHVZHWWDWTJX"
"GHJQVTQXGTQGZWVDDZHGDDHGQQGVTZXZTVGJG"
Returns: "HXHVZHWWDGWTJXHJQVTQXGTQGZWVDDZHGDDHGQQGVTZXZTVGJG"
"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
"AAAAAAAAAAAAAAAAAAAAAAAAA"
"AAAAAAAAAAAAAAAAAAAAAAAAA"
Returns: "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
"AB"
"A"
"B"
Returns: "AB"
"??????????????????????????????????????????????????"
"AAAAAAAAAAAAABPBBBBBFBCCC"
"AAAAAAAAAAAABBABBZBBBBCCC"
Returns: "AAAAAAAAAAAAAAAAAAAAAAAAABBABBBPBBBBBFBCCCZBBBBCCC"
"WHATT?"
"THET"
"WA"
Returns: ""
"AA??"
"AZ"
"AX"
Returns: "AAXZ"
"??????????????????????????????????????????????W???"
"FEWFKFEWFKFEWFKFEWFKFEWFK"
"BABCDBABCDBABCDBABCDBABCD"
Returns: "BABCDBABCDBABCDBABCDBABCFEWFKFEWFKFEWFKFEWFKFEWDFK"
"??????????????????????????????????K???????????????"
"KKKKKKKKKKKKKKKKKKKKKK"
"KKKKKKKKKKKKKKKKKKKKKKKKKKKK"
Returns: "KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK"
"???B?????A???B?????A???B?????A???B?????A???B?????A"
"AAABAABAAAAABAABAAAABAA"
"BBBABBABBBBBABBABBBBABBAAAA"
Returns: "AAABAABAAAAABBAABAAABBABBABBBABBABBABBBABBABABAAAA"
"???B????F????????N???????????????????Q??????X???"
"ABCDEFGHIJKLNOPQITUVWXYZ"
"ABCDEFGHIJKLMNPQSTUVWXYZ"
Returns: "AABBCCDEFDEGHIJKLNFGHIJKLMNOPPQITUVWXQSTUVWYXYZZ"
"Q"
"A"
""
Returns: ""
"AB"
""
"BA"
Returns: ""
"????K??????????????D???K???K????????K?????K??????D"
"KKKKKDKKKDKKDDKDDDKDKK"
"KDKDDKKKDDKDDKKKDKDKKDDDDDDD"
Returns: "KDKDKDKKKDDKDDKKKDKDKKKKDKKKDKKDDKDDKDKDDDKDDDDKKD"