Generalized Abbreviation

Easy
0/40
Average time to solve is 15m
profile
Contributed by
22 upvotes
Asked in company
Google inc

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”].
Detailed explanation ( Input/output format, Notes, Images )

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}.
Hint

Recursively trying to get all the string by noting count of current string length.

Approaches (1)
Backtracking

Approach: The idea is to use backtracking to generate all the generalised abbreviations of the given string.

 

Complete Algorithm:

  1. Make a recursive helper function which will receive 4 parameters that are: string ‘STR’, a string ‘TEMP’, an integer ‘INDEX’ and an integer ‘COUNT’.
  2. Declare a global array/list of strings say ‘ANS’.
  3. Base Case :
    • If ‘INDEX’ is greater or equal than the size of ‘STR’ then do:
      • Check the value of ‘COUNT’:
        • If ‘COUNT’ is greater than 0 then append ‘COUNT’ into ‘TEMP’.
      • Append the string ‘TEMP’ into ‘ANS’ and return.
  4. Recursive calls:
    • We will make a recursive call without appending anything into ‘TEMP’ and just increasing both ‘INDEX’ and ‘COUNT’ by 1.
    • We have two more cases here depending on the value of ‘COUNT’:
      • If ‘COUNT’ is greater than 0:
        • Append ‘COUNT’ in ‘TEMP’.
        • Set ‘COUNT’ = 0.
        • Increase ‘INDEX’ by 1.
        • Make a recursive call with updated variables.
      • If ‘COUNT’ is equal to 0:
        • We will make a recursive call appending ‘STR[INDEX]’ into ‘TEMP’ and increasing both ‘INDEX’ and ‘COUNT’ by 1.
  5. Return ‘ANS’:
Time Complexity

O(2 ^ N), where N is the size of string ‘STR’.

 

As for each recursive call, we are making further 2 calls and increasing ‘INDEX’ by 1 till it reaches ‘N’ thus raising time complexity to O(2 ^ N).

Space Complexity

O(N), where N is the size of string ‘STR’.

 

As total number of strings will be 2 ^ N and Space used by the recursion stack is also O(N). Thus Space complexity to O(N).

Code Solution
(100% EXP penalty)
Generalized Abbreviation
Full screen
Console