UPSUB - Up Subsequence
If x = a0a1a2...an-1 is a string where ai denotes the character at index i, a subsequence aj0aj1aj2...ajn is called an upsubsequence if aj0 <= aj1 <= aj2 <= ... <= ajn and j0 < j1 < j2 < ... < jn.
A maximal upsubsequence of a string is defined as the upsubsequence of maximum length. BuggyD observes that a string x can have many maximal upsubsequences. Help him find all the maximal upsubsequences in x.
Input
The first line of the input contains an integer t, the number of test cases. t test cases follow.
Each test case consists of a single line containing a string x, where the length of x is no more than 100. x will not contain any spaces, tabs or other whitespace characters.
Output
For each test csae, output all of the maximal upsubsequences of x in lexicographical order. Print a blank line after each test case.
Example
Input: 1 abcbcbcd Output: abbbcd abbccd abcccd
hide comments
Shubham:
2016-05-18 17:46:30
solve TRIP first :D :D |
|
Ankit:
2015-10-15 18:04:26
moving backwards will automatically give sorted order :) |
|
Praneeth.N:
2015-02-26 02:36:14
I am not sure why the problem is giving wrong answer inspite of covering all the cases...Can some one kindly give some hints or a test case where there is chance of getting wrong answer.. |
|
Zen:
2014-08-19 10:54:55
:D
|
|
kipoujr:
2011-10-19 18:20:57
You forgot to place a '\n' character at the end of the file! Please correct. |
Added by: | Matthew Reeder |
Date: | 2006-10-30 |
Time limit: | 0.309s |
Source limit: | 30000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | Al-Khawarizm 2006 |