Abbreviation 1 - Using Bits
Try First, Check Solution later1. 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.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
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
* 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.
Asked in Companies