Connection Status:
Competition Arena > MergeStrings

MergeStrings

SRM 615 · 2013-12-22 · by snuke

SRM 615 · 2013-12-22 · by snuke · Dynamic Programming
Class Name: MergeStrings
Return Type: String
Method Name: getmin
Arg Types: (string, string, string)
Problem Statement

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.

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
0)
"??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.

1)
"WHAT?"
"THE"
"WA"
Returns: ""

None of the strings obtained by shuffling "THE" and "WA" matches "WHAT?".

2)
"PARROT"
"PARROT"
""
Returns: "PARROT"

One of A and B may sometimes be empty.

3)
"???????????"
"AZZAA"
"AZAZZA"
Returns: "AAZAZZAAZZA"
4)
"?"
""
"X"
Returns: "X"

Submissions are judged against all 67 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class MergeStrings with a public method string getmin(string S, string A, string B) · 67 test cases · 2 s / 256 MB per case

Submitting as anonymous