LargestSubsequence

SRM 518 · 2011-05-25 · by omeometo

SRM 518 · 2011-05-25 · by omeometo · Greedy, String Manipulation

Show categories

Class Name: LargestSubsequence

Return Type: String

Method Name: getLargest

Arg Types: (string)

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.

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"

"zzyyxxwwvvuuttssrrqqppoonnmmllkkjjiihhggffeeddccaa"
Returns: "zzyyxxwwvvuuttssrrqqppoonnmmllkkjjiihhggffeeddccaa"

Remove no character.

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

Coding Area

Language: C++17 · define a public class LargestSubsequence with a public method string getLargest(string s) · 160 test cases · 2 s / 256 MB per case