The Last Word (Small)
Time limit5sMemory limit512 MB
Given a string S, insert each letter at the front or back of the word as it arrives, and find the alphabetically largest word obtainable.
- Level
Medium5 of 10
- Topics
- Greedy, String, Implementation, Brute force
- Solved
- No attempts yet
Problem
On the game show The Last Word, the host begins a round by showing the contestant a string S of uppercase English letters. The contestant has a whiteboard which is initially blank. The host then presents the letters of S one by one, in the order in which they appear in S. When the host presents the first letter, the contestant writes it on the whiteboard; this counts as the first word in the game (even though it is only one letter long). After that, each time the host presents a letter, the contestant must write it at the beginning or the end of the word on the whiteboard before the host moves on to the next letter (or to the end of the game, if there are no more letters).
For example, for S = CAB, after writing the word C on the whiteboard, the contestant could make one of the following four sets of choices:
- put the
AbeforeCto formAC, then put theBbeforeACto formBAC - put the
AbeforeCto formAC, then put theBafterACto formACB - put the
AafterCto formCA, then put theBbeforeCAto formBCA - put the
AafterCto formCA, then put theBafterCAto formCAB
The word on the whiteboard after the contestant has written all of the letters of S under these rules is called the last word. The contestant wins if their last word is the last entry in an alphabetically sorted list of all the last words that could have been produced. In the example above, the winning last word is CAB (which happens to be the same as the original word). For a game with S = JAM, the winning last word is MJA.
You are the next contestant on this show, and the host has just shown you the string S. What is the winning last word that you should produce?
Input
The first line of the input gives the number of test cases, T. T test cases follow. Each consists of one line with a string S.
Limits
- length of S
- S consists of uppercase English letters only.
Output
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the winning last word, as described in the statement.