Write an algorithm for string compression using counts of repeated characters
E.g. aaaaarrrrbbb will become a5r4b3
Additional note: if the new compressed string is is bigger than the original string, return original string.
Engineering Full Stack Apps with Java and JavaScript
Write an algorithm for string compression using counts of repeated characters
E.g. aaaaarrrrbbb will become a5r4b3
Additional note: if the new compressed string is is bigger than the original string, return original string.
what should be the output if the string is "aaabbaazz"?
Option1: a3b2a2z2
Option2: a5b2z2
Good question, but I will make you only answer this.
Important property of any compression algorithm in real world is that it should be able to reconstruct the original string from the compressed form.
From which one of the above compressed forms (a3b2a2z2 and a5b2z2) do you think you can reconstruct the original string above (aaabbaazz) exactly as it is?
Note: Please answer even if you understood.
Thanks for clearing my doubt.. We can reconstruct the string only when we construct like a5b2a2z2..
Here is my solution:
The time complexity is O(n)...
Your suggestions to improve performance is highly appreciated..
public class StringCompression {
public static void main(String[] args) {
String input = "aaaaarraarrbbb";
// SOLUTION 1
char[] inputChArr = input.toCharArray();
StringBuffer sb = new StringBuffer();
boolean[] boolArr = new boolean[255];
int count = 0;
for(int i = 0 ;i<inputChArr.length;i++) {
if(boolArr[inputChArr[i]]) {
count++;
}
else {
boolArr[inputChArr[i]] = true;
if(i!=0 && inputChArr[i] != inputChArr[i-1]) {
boolArr[inputChArr[i-1]] = false;
sb.append(count + "" + inputChArr[i]);
//sb.append(inputChArr[i]);
}else {
//For first Character alone
sb.append(inputChArr[i]);
}
count = 1;
}
}
sb.append(count);
System.out.println("Input String: " + input + "\nCompressed String: " + sb);
}
}
clalam : can you please explain your first solution ?
Please check the explanation below:
Reply me for any doubts..
1) I am just marking the first occurance of each unique character as "true"(255 unique char possiblities in ASCII).
2) so, from second iteration onwards, it will check in the boolean array for the charcter is already present or not..
a) if it is already present and repeating just increment the count.
b) otherwise mark next char as "true" and previous char as "false"(as the it may come again) and construct your output by using stringbuffer append.
c) repeat till end of the array.
3) Print the StringBuffer value outside the loop..
for this string: "aaaaarraarrbbb"
for first iteration
booleanArr[a(which is 97)] will be true and count will be 1.
from second iteration onwards.. count will be incremented till 5th iteration as booleanArr[a] is true during these iterations.
6th iteration, it will go to else part and mark booleanArr[r] as true and booleanArr[a] as false(since a may come after r as in the above input). At this point, your output string contains "a5r"
the above steps will be repeated till end of the array and finally you will have the required result in your output string..
how does this :
sb.append(count);
after the for loop works .... means i know its correct but how you appended only count ?
If you observe else if condition, I am appending count of previous char and current char, that means when "r" comes first time, the SB will become "a5r". But we should also append count of last char of the string where as my condition work here since it comes out of for loop but I have the count of last char in my count variable. Simply append that to your output string..
If you wanna play with it,just try to remove that statement alone and you won't see the count of last character.