3

Ninja and Strings

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

Problem Statement

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

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

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”
``````
Console