# Abbreviation 1 - Using Bits #### 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.Note - Use bit manipulation`
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

The problem here deals with generating all the abbreviations of a string here by using bit manipulation. Earlier we have solved this problem using recursion now here we will implement a solution making use of bit manipulation concepts.

The abbreviation here is an alpha-numeric type where characters are mixed with the digits. The digits represent the number of skipped characters of a selected substring. Henceforth, whenever a substring of characters is skipped, it is replaced with the digit denoting the number of characters in the substring. There may be any number of skipped substrings of a string. No two substrings should be adjacent to each other. Hence, no two digits are adjacent to the result.

Let us consider an example to understand the problem better,

String -> pep

Abbreviations:

pep

pe1

p1p

p2

1ep

1e1

2p*

3

* Note: 11p is not valid because no two digits should be adjacent,

2p is the correct one because pe is a substring, not p and e individually.

Let us try to draw an analogy with bit manipulation to approach to the solution:

000 -> pep

001 -> pe1

010 -> p1p

011 -> p2

100 -> 1ep

101 -> 1e1

110 -> 2p

111 -> 3

This pattern clearly indicates that abbreviations can be easily obtained from the binary representation of numbers from 0 to 2str.length() - 1. Here from 0 to 7.

The solution to the problem is to take every number from 0 to 2str.length() - 1 and for every number we need to keep a check of its binary digit, if the digit is 0 then we need to print the corresponding character and if the digit is 1 then we need to skip the corresponding character and increment the counter variable. The counter variable is responsible for all the numeric values in the abbreviation, also when the digit is zero we need to consider the count too if the count is greater than 0 say in the case of 100 at index 1 we will have count = 1 so we will firstly print the count, then reset the count variable to 0 and thereafter we will add the character e to the result. Also after traversing the bits if there is still any unsettled count value left then we need to settle it at the end of the resultant string, in the case of 111 after string end, we have count = 3 and resultant string null so we add 3 to the resultant string and henceforth we obtain 3 as the abbreviation.

Time Complexity: O(n2n)

The time complexity for the function is exponential as we need to consider all the sub-sequences which takes 2n time and then for every subsequence we need to traverse the string which takes linear time.

Space Complexity: O(1)

The space complexity for the function is constant.

• Related Topics

Run

Run
Id Name