Prev   Next

Abbreviation 1 - Using Bits







"It's impossible," said Pride. "It's risky." said Experience. "It's pointless," said Reason. "Give it a try!" whispered the Heart.

Abbreviation 1 - Using Bits

Welcome Back Reader!

In this article we will discuss the next problem based on 'Bit Manipulation' i.e. 'Abbreviation 1 - Using Bits.

Earlier we solved this problem using Recursion and backtracking. But here, we will be solving this problem using Bit Manipulation.

Before you move any further, it is advised that you give this problem a fair try. Let's jump to the problem.

Importan Link : Problem Link, Solution Video Link

Understanding the problem:

In this problem you are given a word.

All you have to do is to generate all abbreviations of that word.

Note: Use bit manipulation

For example:

Sample Input: pep

Sample Output: pep pe1 p1p p2 1ep 1e1 2p 3 (in different lines)

HOW?

First of all, generate all the binaries of the length equal to the length of the input string.

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 (zero), we will use the character of the string at that position and whenever the bit is ON (one), we will count all the ON (one) bits that are together and then replace them with the count of the ON (one) bits.
  • The number of abbreviations will be equal to 2^n, where n = length of the string (as the number of binaries with given n is equal to 2^n).
  • In the above example n = 3, therefore the number of abbreviations will be 8 (2^3 = 8).

For more clarity of this part, watch this part of the video.

Approach:
  • The above pattern for 'pep' clearly indicates that abbreviations can be easily obtained from the binary representation of numbers from 0 to (2^str.length() - 1). Here from 0 to 7 (as str.length() = 3).
img
  • The solution to the problem is to take every number from 0 to (2^str.length() - 1).
  • It's important to note that we need to check the bits of the binary number from left to right so that it can correspond to the order of the input string.
img
  • 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 binary, '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.

For more clarity of this part, watch this part of the video.

Let's try to code this!
public static void solve(String str){ for(int i = 0; i < (1 << str.length()); i++){ //1 StringBuilder sb = new StringBuilder(); int count = 0; for(int j = 0; j < str.length(); j++){ //2 char ch = str.charAt(j); int b = str.length() - 1 - j; if((i & (1 << b)) == 0){ //3 if(count == 0){ //4 sb.append(ch); } else { //5 sb.append(count); sb.append(ch); count = 0; } } else { //6 count++; } } if(count > 0){ //7 sb.append(count); } System.out.println(sb); //8 } }
java; true";

Code Explained:

  1. A for loop is initiated from 0 to (1 << str.length()) (which gives binary number for 2 raise to the power length of string) Inside this loop, first of all define a string builder, sb and an int, count to 0.
  2. Then for every binary we run a 'for' loop on the length of the input string and process the input string corresponding to the binary of 'i'. Inside this for loop, we capture the character at jth index of the string and then we store a number in variable b which is equal to str.length() - 1 - j (so that we can read the binary from right to left instead of left to right).
  3. Then we check if i & (1<<b) equal to 0. If it is zero it means that bth bit of i is off (zero).
  4. If the condition is true then we check whether the count is 0 or not. If it is zero then we simply append the character in the sb.
  5. If not then first append count in the sb and then append the character in sb.
  6. If not then first append count in the sb and then append the character in sb.
  7. After coming out of the for loop, we check if the count is greater than 0. If it is greater than 0 then we append the count in the sb.
  8. Then we finally print the sb.

For more clarity of this part, watch this part of the video.

import java.io.*; import java.util.*; public class Main { public static void solve(String str){ for(int i = 0; i < (1 << str.length()); i++){ StringBuilder sb = new StringBuilder(); int count = 0; for(int j = 0; j < str.length(); j++){ char ch = str.charAt(j); int b = str.length() - 1 - j; if((i & (1 << b)) == 0){ if(count == 0){ sb.append(ch); } else { sb.append(count); sb.append(ch); count = 0; } } else { count++; } } if(count > 0){ sb.append(count); } System.out.println(sb); } } public static void main(String[] args) { Scanner scn = new Scanner(System.in); String str = scn.nextLine(); solve(str); } }
java; true";
Complexities:
Time Complexity:

O(n * (2^n))

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

Space Complexity:

O(1)

The space complexity for the function is constant.

We hope that this article was helpful. If somehow you are finding it difficult to understand this problem then we advise you to watch our video lecture of this problem.
Trust me it will just get easier to understand after you have watched the solution video.
You can contact us via our website. Doubts, suggestions and feedback are always welcomed.
It is also advised that you follow the sequence of modules and questions which is there on our website.
Keep practicing more and more problems daily. Meditate enough on each step of each problem.
All the best for your optimistic future!
Happy Coding!

Abbreviations
Author: Nikita Aggarwal
 
Run
Id Name