Abbreviation 1  Using Bits
1. You are given a word.Input Format
2. You have to generate all abbrevations of that word.
Note  Use bit manipulation
A string representing a wordOutput Format
Check the sample ouput and question video.Question Video
1 <= length of string <= 32Sample Input
pepSample Output
pep
pe1
p1p
p2
1ep
1e1
2p
3

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 alphanumeric 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 subsequences 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.

Asked in Companies

Related Topics