LargestSubsequence | Topcoder Archive

Problem Statement

For Strings x and y, we say y is a subsequence of x if y can be obtained from x by erasing some (possibly all or none) of the letters in x. For example, "tpcdr" is a subsequence of "topcoder", while "rt" is not.

Given a String s, return the lexicographically largest subsequence of s.

Definition

Class:: LargestSubsequence
Method:: getLargest
Parameters:: String
Returns:: String
Method signature:: String getLargest(String s)
(be sure your method is public)

Notes

For strings x and y, x is said to be lexicographically larger than y if y is a prefix of x or y has a smaller character than x at the first position where they differ. Order of characters is defined as the order of ASCII codes: 'a' < 'b' < ... < 'z'.

Constraints

s will contain between 1 and 50 characters, inclusive.
Each character in s will be a lowercase letter ('a'-'z').

Examples

```
"test"
```
```
Returns: "tt"
```
All subsequences listed in lexicographical order are "" (empty string), "e", "es", "est", "et", "s", "st", "t", "te", "tes", "test", "tet", "ts", "tst" and "tt". So return "tt".
```
"a"
```
```
Returns: "a"
```
There are only two subsequences, "" and "a".
```
"example"
```
```
Returns: "xple"
```

"aquickbrownfoxjumpsoverthelazydog"

Returns: "zyog"

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.