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

  • Asked in Companies
  • Related Topics






Video Solution

Code Solution

Run
 
Run
Id Name