Compress an ASCII string Given an ASCII string create a 'compressed' version of it. For example, aabccccddddddde would output a2bc4d7e whereas abc would output abc.


This is how I've implemented it. Is there a smarter way to do it without the need for two for loops?

import java.util.LinkedHashMap;
import java.util.Set;

public class CompressString {

  private static String compressString(String s) {
    LinkedHashMap&lt;Character, Integer&gt; charCountMap = createCharacterCountMap(s);

    StringBuilder result = new StringBuilder();
    Set&lt;Character&gt; keySet = charCountMap.keySet();
    for(Character c: keySet) {
      int val = charCountMap.get(c);
      if(val == 1) {
        result.append(c);
      } else {
        result.append(c.toString() + val);
      }
    }
    return result.toString();
  }

  private static LinkedHashMap&lt;Character, Integer&gt; createCharacterCountMap(String s) {
    char[] charArray =  s.toCharArray();
    int[] charCountArray = new int[128];
    LinkedHashMap&lt;Character, Integer&gt; charCountMap = new LinkedHashMap&lt;Character, Integer&gt;();
    for(int i=0; i&lt;charArray.length; i++) {
      int intVal = charArray[i];
      charCountArray[intVal]++;
      charCountMap.put(charArray[i], charCountArray[intVal]);
    }
    return charCountMap;
  }

  public static void main(String[] args) {
    String s1 = "aabccccddddddde";
    String s2 = "abc";
    System.out.println(compressString(s1));
    System.out.println(compressString(s2));
  }

}
I'm commenting on the edited version only. It's fine, but

char cur = s.charAt(0);


throws for the empty string. You could special case it, but in general, it's better to do it the other way: Maintain a state containing a lastCharacter and a count. The initial state has count=0 (lastCharacter is initially arbitrary).

StringBuilder result = new StringBuilder();


You could pre-size it using s.length as it's a sure upper bound. Not very important except maybe for long strings.

 result.append(cur);


Your approach needs this action at the beginning, while mine needs it at the end. You need also a complicated condition like if((i == s.length() - 1) &amp;&amp; (count &gt; 1)) which I don't want to understand.

for(int i=1; i&lt;s.length(); i++) {
  char nxt = s.charAt(i);


Saving a single character compared to next is not worth it, is it?



You should also fix your spacing, especially add a space after for and if. Use your IDE.



I'd propose something like (my spacing is not conform, please ignore)

private static String compressString(String s) {
    StringBuilder result = new StringBuilder();
    int count = 0;
    char last = ' '; // doesn't matter
    for (int i=0; i&lt;s.length(); i++) {
        char c = s.charAt(i);
        if (count==0) {
            last = c;
            count = 1;            
        } else if (c==last) {
            count++;
        } else if (count==1) {
            // While this ensures the string never grows,
            // it also creates the ambiguity mentioned below.
            result.append(last);
            last = c;
        } else {
            result.append(last).append(count);
            last = c;
            count = 1;            
        }
    }
    if (count&gt;0) {
        result.append(last).append(count);
    }
    return result.toString();
}




Note that whenever the string contains digits, it gets irreversibly mangled:

`11` -&gt; `12`
`12` -&gt; `12`