30/03/2017

[Java] Compress string by counting character repetitions

Here is a simple method to compress a string by counting the character repetitions and producing a new string  containing that information; if the compressed string is longer, just keep the original one.

The idea is simply to walk the string keeping track of the current count for each item we encounter in two separate arrays. Then we walk both arrays at the same time and concatenate each character with the number of appearances he had; lastly we check if the compressed string is shorter and decide what to return.

You can check my Gist for the code (stringCompress) with tests:

 public static String stringCompress(String s){  
     if(s == null || s.length() <= 1) return s;  
   
     int[] counts = new int[s.length()];  
     char[] chars = new char[s.length()];  
     char c;  
     int j = 0;  
   
     counts[0] = 1;  
     chars[0] = s.charAt(0);  
   
     //for each character in string, count how many times it appears  
     for(int i = 1; i < s.length(); i++){  
       c = s.charAt(i);  
   
       if(c == chars[j]) counts[j]++;  
       else{  
         j++;  
         chars[j] = c;  
         counts[j] = 1;  
       }  
     }  
   
     //if we compressed the string a bit, then our arrays have some space left, mark the premature end  
     if(j < counts.length - 1) counts[++j] = -1;  
   
     //we do not want to create a new String everytime while we concatenate  
     StringBuilder sb = new StringBuilder();  
   
     j = 0;  
     while(j < counts.length){  
       if(counts[j] == -1) break;  
       //for each character in original string, concatenate it alongside the number of occurrences  
       sb.append(chars[j]);  
       sb.append(counts[j]);  
       j++;  
     }  
   
     //if the compressed string is longer, return original string instead  
     if(sb.length() > s.length()) return s;  
   
     return sb.toString();  
   }  

No comments:

Post a Comment

With great power comes great responsibility