MakeUnique

TCO '03 Semifinals 3 · 2003-10-07 · by dgoodman

TCO '03 Semifinals 3 · 2003-10-07 · by dgoodman · Dynamic Programming, String Manipulation

Show categories

Class Name: MakeUnique

Return Type: String

Method Name: eliminated

Arg Types: (string)

Problem Statement

Given a sequence of uppercase letters, we want to remove all but one occurrence of each letter, doing it in such a way that the remaining letters are in alphabetical order. Of course, there may be no way to do this, but if there is, we want to know which letters to remove.

Create a class MakeUnique that contains a method eliminated that is given a String original, and returns original with the eliminated letters replaced with periods ('.'). The remaining letters must be in alphabetical order.

If there is no way to do this, return a String with length 0.

If there are several ways to do this, choose the one with the shortest length between the first and last remaining letters. If there are still several ways, return the String among these that comes earliest lexicographically ('.' comes earlier than any letter in the ASCII sequence).

Constraints

original will contain between 1 and 50 characters inclusive
each character in original will be an uppercase letter 'A'-'Z'

Examples

"ABBBXCXABCX"
Returns: ".......ABCX"

The 4 letters ABCX must remain, and in that order. "AB...CX...." would also leave these letters in the appropriate order, but the length between the first and last remaining letters would be longer than in the given answer.

"ABBBXCXABCB"
Returns: "A..B.CX...."

"AB...CX...." and "A.B..CX...." are also possible and have the same length between first and last remaining letters, but they come later lexicographically than the given answer.

"ABBBXCABCB"
Returns: ""

There is no way to eliminate letters and end up with C before X.

"AABACBXABX"
Returns: ".AB.C.X..."

"CABDEAFDEGSDABCDEADFGSEFBGS"
Returns: "............ABCDE..FGS....."

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

Coding Area

Language: C++17 · define a public class MakeUnique with a public method string eliminated(string original) · 46 test cases · 2 s / 256 MB per case