3

Ninja and Strings

Difficulty: MEDIUM
Contributed By
Avg. time to solve
15 min
Success Rate
85%

Problem Statement

Ninja has been given a string ‘STR’ containing lowercase english alphabets. He wants to generate all the possible subsequences of the ‘STR’ in lexicographically sorted order.

For example: For ‘STR’ = “abc” following are the subsequences in lexicographically sorted order:

[“a”], [“ab”], [“abc”], [“ac”], [“b”], [“bc”], [“c”]

Ninja is busy with some other task so he asks you for help.

Can you help Ninja to generate all the possible subsequences of the given string ‘STR’ in lexicographically sorted order?

Input Format:
The first line of input contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.

The first and the only line of each test case contains a string ‘STR’.
Output Format :
For each test case, print all the possible subsequences of the given string ‘STR’ in lexicographically sorted order.

Print the output of each test case in a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints:
1 <= ‘T’ <= 100
1 <= |STR| <= 10 

Where |STR| represents the length of ‘STR’.

Time Limit: 1 sec
Sample Input 1:
2
aba
aaa
Sample Output 1:
a a aa ab aba b ba 
a a a aa aa aa aaa

Explanation Of Sample Output 1:

For test case 1: 
In this sample test case, the following are the possible subsequences of the given ‘STR’:  
1. “a”
2. “b”
3. “a”
4. “ab”
5. “ba”
6. “aa”
7. “aba”

After arranging these subsequences into lexicographically sorted order, we get:
“a”, “a”, “aa”, “ab”, “aba”, “b”, “ba” 

For test case 2: 
In this sample test case, the following are the possible subsequences of the given ‘STR’:
1. “a”
2. “a”
3. “a”
4. “aa”
5. “aa”
6. “aa”
7. “aaa”

After arranging these subsequences into lexicographically sorted order, we get:
“a”, “a”, “a”, “aa”, ”aa”, “aa”, “aaa” 
Sample Input 2:
2
x
zxy
Sample Output 2:
x
x xy y z zx zxy zy

Explanation Of Sample Output 2:

For test case 1: 
In this sample test case, there is only one possible subsequence of the given ‘STR’:  
1. “x”

For test case 2: 
In this sample test case, the following are the possible subsequences of the given ‘STR’:  
1. “z”
2. “zx”
3. “zxy”
4. “x”
5. “xy”
6. “y”
7. “zy”

After arranging these subsequences into lexicographically sorted order, we get:
“x”, “xy”, “y”, “z”, “zx”, “zxy”, “zy”
Reset Code
Full screen
copy-code
Console