TheLargestString

TCO13 Round 2A · 2013-02-19 · by Vasyl[alphacom]

TCO13 Round 2A · 2013-02-19 · by Vasyl[alphacom] · String Manipulation

Show categories

Class Name: TheLargestString

Return Type: String

Method Name: find

Arg Types: (string, string)

Problem Statement

John has two strings s and t of equal length. He can choose a set of positions (possibly empty) and erase characters at these positions in both s and t. Then he writes down the concatenation of what remained of the strings: first the letters we kept from s, in their original order, then the letters we kept from t, again in their original order.

Return the lexicographically largest string John can get at the end.

Notes

String A is lexicographically smaller than string B if either A is a proper prefix of B, or if there is an integer i such that the first i characters of A match the first i characters of B, and character i+1 of A is smaller than character i+1 of B.

Constraints

s will contain between 1 and 47 characters, inclusive.
s and t will contain the same number of characters.
s will contain only lowercase English characters ('a'-'z').
t will contain only lowercase English characters ('a'-'z').

Statement by TopCoder, Inc. — view the original on the archive.

Examples

"ab"
"zy"
Returns: "by"

There are four options here: Do not erase anything. The resulting string would be "abzy". Erase both first characters. The resulting string would be "by". Erase both last characters. The resulting string would be "az". Erase all characters. The resulting string would be empty. Among all possible results "by" is the lexicographically largest one.

"abacaba"
"zzzaaaa"
Returns: "cbaaaa"

"x"
"x"
Returns: "xx"

"abbabbabbababaaaabbababab"
"bababbaabbbababbbbababaab"
Returns: "bbbbbbbbbbbbbbbbbbaaab"

"bo"
"yg"
Returns: "og"

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

Coding Area

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