MergeStrings | Topcoder Archive

Problem Statement

Guts is a slow loris who likes to play with strings.

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].

You are given Strings S, A, and B. Strings A and B contain only letters, string S can also contain multiple copies of the '?' (question mark) character. The '?' is a wildcard that represents any single letter. Guts wants to shuffle strings A and B in such a way that the resulting string matches S.

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 String instead.

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"

"????K??????????????D???K???K????????K?????K???????"

"KKKKKDKKKDKKDDKDDDKDKK"

"KDKDDKKKDDKDDKKKDKDKKDDDDDDD"

Returns: "KDKDKDKKKDDKDDKKKDKDKKDKDDDKDDDKKDKKKDKKDDKDDDKDKK"

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.