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).
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.
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.
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.
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).
Then we check if i & (1<<b) equal to 0. If it is zero it means that bth bit of i is off (zero).
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.
If not then first append count in the sb and then append the character in sb.
If not then first append count in the sb and then append the character in sb.
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.
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!