String Compression
Implement a method to perform basic string compression using the counts of repeated characters.
For example, the string
String input = "aabcccccaaa";
String output = "a2b1c5a3";
If the “compressed” string would not become smaller than the original string, your method should return the original string. You can assume the string has only uppercase and lowercase letters (a - z).
Link here to the repo to solve the problem
👉👌 Tips
Do the easy thing first. Compress the string, then compare the lengths.
Be careful you are not repeatedly concatenating strings together. This can be very inefficient.
👊 Solution 1
A simple solution concatenating could work, however it would not be efficient. Its runtime would be O (S + K ^ 2), where S is the length of the String and K is the number of character sequences. For example, if the String is "aabccdeeaa" there would be 6 character sequences. Remember also that concatenating strings without a StringBuilder takes O(N ^ 2).
String ineficientSolution(String str) {
String compressed = "";
int count = 0;
for (int i = 0; i < str.length(); i++) {
count++;
if (i + 1 >= str.length() && str.charAt(i) != str.charAt(i + 1)) {
compressed+= "" + str.charAt(i) + count;
count = 0;
}
}
return compressed.length() < str.length() ? compressed : str;
}
👊 Solution 2
Let’s optimise the first solution this time using a StringBuilder:
String stringBuilderSolution(String str) {
int length = str.length();
char current = str.charAt(0);
int count = 0;
StringBuilder compressed = new StringBuilder();
for (int i = 0; i < length; i++) {
char c = str.charAt(i);
if (c == current) {
count++;
} else {
compressed.append(current).append(count);
current = c;
count = 1;
}
}
compressed.append(current).append(count);
return compressed.length() < length ? compressed.toString() : str;
}
Borrowed question from the book “Cracking the coding interview”