String Compression using count of repeated characters – Run Length Encoding

Objective: Write an algorithm to compress the given string by using the count of repeated characters and if new compressed string length is not smaller than the original string then return the original string.

Example:

Input String : ssssuuuummmmmmiiiittttttttttttt
Compressed String : s4u4m6i4t13

Input String : Jaain
Compressed String : Jaain (Since compressed string is length is greater than original string)

Input: A String

Output: either A compressed string or original string whichever us smaller.

Approach:

  • Create a StringBuffer sb, int count
  • Navigate the string taking each character at a time.
  • If you find the same characters increase the count.
  • if not then append the character and its count to the string buffer sb.
  • reset the count value.
  • Compare the length of compressed String and original and whichever is smaller return that string.

Complete Code:

public class StringCompression {
public String compression(String s1){
StringBuffer sb = new StringBuffer();
int count =1;
char prev = s1.charAt(0);
for(int i=1;i<s1.length();i++){
char curr =s1.charAt(i);
if(prev==curr){
count++;
}else{
sb.append(prev);
sb.append(count);
prev = curr;
count=1;
}
}
sb.append(prev);
sb.append(count);
if(s1.length()<sb.length()){
return s1;
}else{
return sb.toString();
}
}
public static void main(String args[]){
String s1 = "ssssuuuummmmmmiiiittttttttttttt";
StringCompression sc = new StringCompression();
System.out.println("Compression of " + s1 + " is : " +sc.compression(s1));
s1 = "Jaain";
System.out.println("Compression of " + s1 + " is : " +sc.compression(s1));
}
}


Output:

Compression of ssssuuuummmmmmiiiittttttttttttt is : s4u4m6i4t13
Compression of Jaain is : Jaain