2

Generalized Abbreviation

Difficulty: EASY
Contributed By
Shrey Pansuria
Avg. time to solve
15 min
Success Rate
85%

Problem Statement

You are given a string ‘STR’ consisting of English lowercase letters.

Your task is to find out all the generalised abbreviations of ‘STR’ and print an array/list of these abbreviations sorted in increasing order.

Note:

A string is said to be a generalised abbreviations string of ‘STR’ if we remove a substring of length ‘X’ from ‘STR’ and put the number ‘X’ at the place of the removed substring.

We can not remove two consecutive substrings or we can say generalised abbreviations will never have two consecutive numbers.

For example:

If ‘STR’ = “abc”,
Sorted generalized abbreviations of ‘STR’ are: [“1b1”, “1bc”, “2c”, “3”, “a1c”, “a2”, “ab1”, “abc”].

Input Format:

The first line of input contains a single integer T, representing the number of test cases.
Then the T test cases follow.

The first and the only line of each test case contains a string ‘STR’.

Output format:

For every test case, print all the generalised abbreviations of ‘STR’ separated by a single space.

The output of each test case is printed in a separate line.

Note :

You don’t have to print anything. It has already been taken care of. Just implement the given function. 

Constraints:

1<= T <=10
1<= |STR| <= 20

Where |STR| is length of String 'STR'.

Time limit: 1 sec

Sample Input 1:

2
ab
xyz

Sample Output 1:

1b  2  a1  ab
1y1  1yz  2z  3  x1z   x2   xy1   xyz

Explanation Of Sample Input 1:

For test case 1:
"ab" can be written as {1b,  2,  a1,  ab}.

For test case 2:
"xyz" can be written as {1y1, 1yz,  2z,  3,  x1z,   x2,   xy1,   xyz}.

Sample Input 2:

2
n
code

Sample Output 2:

1 n
1o1e  1o2  1od1  1ode  2d1  2de  3e  4  c1d1  c1de  c2e  c3  co1e  co2  cod1  code 

Explanation Of Sample Input 2:

For test case 1:
"n" can be written as {1, n}.

For test case 2:
"code" can be written as {1o1e,  1o2,  1od1,  1ode, 2d1,  2de,  3e,  4,  c1d1,  c1de,  c2e,  c3,  co1e,  co2,  cod1,  code}.
Reset Code
Full screen
copy-code
Console