TheLargestString | Topcoder Archive

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.

Definition

Class:: TheLargestString
Method:: find
Parameters:: String, String
Returns:: String
Method signature:: String find(String s, String t)
(be sure your method is public)

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

```
"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"

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.