# Abbreviation Using Backtracking #### Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

`1. You are given a word.2. You have to generate all abbrevations of that word.Use recursion as suggested in question video`
Input Format
`A string representing a word`
Output Format
`Check the sample ouput and question video.`
Question Video
Constraints
`1 <= length of string <= 32`
Sample Input
`pep`
Sample Output
`peppe1p1pp21ep1e12p3`

• Editorial

We have to generate all the abbreviations of the string passed as an input.

Example 1 -

Input -

pep

Output -

pep

pe1

p1p

p2

1ep

1e1

2p

3

Example 2  -

Input -

ac

Output -

ac

a1

1c

2

Example 3 -

Input -

a

Output -

a

1

Before proceeding towards the solution, we will first generate all the binaries of the length equal to length of input string.

Let the input string be "pep".

Binaries -

000 -> pep

001 -> pe1

010 -> p1p

011 -> p2

100 -> 1ep

101 -> 1e1

110 -> 2p

111 -> 3

We can observe that whenever the bit is OFF, we will use the character of the string at that position and whenever the bit is ON, we will count all the ON bits  that are together and then replace them with the count of the ON bits.

The number of abbreviations will be equal to 2n , where n = length of the string(as the number of binaries with given n is equal to 2n ).

We can see that this question is like subsequence, we must maintain one more variable which will count the characters that were not included in the subsequence.

Code:

```public static void solution(String str, String asf,int count, int pos){
if(pos == str.length()){
if(count > 0){
asf += count;
}
System.out.println(asf);
return;
}
solution(str, asf + (count > 0 ? count : "" ) + str.charAt(pos), 0, pos + 1); //yes call -> including curr char
solution(str, asf, count + 1, pos + 1); //not including curr char -> just converting letters to a number
}```

java false

Code Explained -

SIGNATURE of the function -

public static void solution (String str, String asf,int count, int pos) {}

str -Input string

asf  - String that stores the answer till index pos at different levels.

count  - store the count of characters that were not included in the subsequence just before the pos index.

pos  - current index.

We will make two calls at each level  -

Call Yes  - Include the character at index pos in asf

Call No -  Do not include the character at index pos in asf.

When we make a NO CALL, we increase the pos variable and not include anything in the asf. We will also increase count variable as we are not including the current character in answer.

When we make a YES CALL, we will check whether the count is more than zero. If the count is more than zero we will add the count and the character at pos index else we will just add the character at pos index. Also, we will make the count variable equal to zero. We are adding the count to the asf as we have to include the characters that we did not add earlier.

We will make YES call before NO call because of the order of output.

YES CALL -

solution (str, asf + (count > 0 ? count : "" ) + str.charAt(pos), 0, pos + 1);

NO CALL  -

solution (str, asf, count + 1, pos + 1);

The above explained method will be clearer by seeing the recursion diagram.

In recursion diagram ,(a | b | c )  a refers to the test string , b refers to the asf and c refers to the count.

Base case -

We will return when pos will be equal to length of the string. Before returning we will print the asf. If the count will be greater than zero, we will append the count to the asf before printing it.

Time Complexity  - O(2^N)

Where N = length of the input string.

As we are making two calls Yes / No at every index until our pos index is equal to the length of the string, therefore the complexity will be exponential and equal to 2 ^ N.

Space Complexity  - O(N)

Where N = length of the input string.

We can observe that maximum depth of recursion tree any time is N. Therefore, the max space occupied at any time will be equal to the N. In the post order, the occupied space in recursion stack will be freed so the space occupied will not exceed N.

• Related Topics

Run

Run
Id Name