TheLargestString
TCO13 Round 2A · 2013-02-19 · by Vasyl[alphacom]
TCO13 Round 2A · 2013-02-19 · by Vasyl[alphacom] · String Manipulation
Problem Statement
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.
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').
Examples
0)
"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.
1)
"abacaba" "zzzaaaa" Returns: "cbaaaa"
2)
"x" "x" Returns: "xx"
3)
"abbabbabbababaaaabbababab" "bababbaabbbababbbbababaab" Returns: "bbbbbbbbbbbbbbbbbbaaab"
4)
"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