LexmaxReplace

SRM 717 · 2017-05-20 · by Arterm

SRM 717 · 2017-05-20 · by Arterm · String Manipulation

Show categories

Class Name: LexmaxReplace

Return Type: String

Method Name: get

Arg Types: (string, string)

Problem Statement

Alice has a string s of lowercase letters. The string is written on a wall.

Alice also has a set of cards. Each card contains a single letter. Alice can take any card and glue it on top of one of the letters of s. She may use any subset of cards in this way, possibly none or all of them. She is not allowed to glue new letters in front of s or after s, she can only replace the existing letters.

Alice wants to produce the lexicographically largest possible string.

You are given the String s. You are also given a String t. Each character of t is a letter written on one of the cards. Compute and return the lexicographically largest string Alice can produce on the wall while following the rules described above.

Notes

Given two distinct strings X and Y of the same length, the lexicographically larger one is the one that has a larger character on the first position on which they differ.

Constraints

s will contain between 1 and 50 characters, inclusive.
t will contain between 1 and 50 characters, inclusive.
s will contain only lowercase English letters ('a' - 'z').
t will contain only lowercase English letters ('a' - 'z').

Examples

"abb"
"c"
Returns: "cbb"

Alice has a single card. This card contains the letter 'c'. The optimal solution is to glue it on top of s[0], producing the string "cbb".

"z"
"f"
Returns: "z"

Here the optimal solution is to do nothing. The card with the letter 'f' will remain unused.

"fedcba"
"ee"
Returns: "feeeba"

"top"
"coder"
Returns: "trp"

"abcdefgh"
"zzz"
Returns: "zzzdefgh"

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

Coding Area

Language: C++17 · define a public class LexmaxReplace with a public method string get(string s, string t) · 35 test cases · 2 s / 256 MB per case