5
\$\begingroup\$

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<Character, Integer> charCountMap = createCharacterCountMap(s);

    StringBuilder result = new StringBuilder();
    Set<Character> 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<Character, Integer> createCharacterCountMap(String s) {
    char[] charArray =  s.toCharArray();
    int[] charCountArray = new int[128];
    LinkedHashMap<Character, Integer> charCountMap = new LinkedHashMap<Character, Integer>();
    for(int i=0; i<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));
  }

}
\$\endgroup\$
  • 3
    \$\begingroup\$ What's aabbaaacca supposed to produce? \$\endgroup\$ – Pimgd Dec 8 '14 at 14:25
  • \$\begingroup\$ What you're doing here is called run-length encoding. Google that for alternative and/or more efficient approaches. \$\endgroup\$ – user29120 Dec 8 '14 at 14:26
  • \$\begingroup\$ @Pimgd good question, tbh I've answered this based on memory of a question in a book I was reading last night. I shall check later to see if it specifies \$\endgroup\$ – PDStat Dec 8 '14 at 14:28
  • \$\begingroup\$ you should also check latest char \$\endgroup\$ – Adem Dec 8 '14 at 15:07
4
\$\begingroup\$

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) && (count > 1)) which I don't want to understand.

for(int i=1; i<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<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>0) {
        result.append(last).append(count);
    }
    return result.toString();
}

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

`11` -> `12`
`12` -> `12`
\$\endgroup\$
3
\$\begingroup\$

Unit testing

First of all, to verify your logic is correct, you need multiple test cases. What you did in the main method is not nearly convenient enough. You have to re-read the output after every change to verify correctness. To really automate the verification, it's best to add test cases, for example:

private String compress(String input) {
    return CompressString.compressString(input);
}

@Test
public void test_a5() {
    assertEquals("a5", compress("aaaaa"));
}

@Test
public void test_empty() {
    assertEquals("", compress(""));
}

@Test
public void test_a() {
    assertEquals("a", compress("a"));
}

@Test
public void test_a3b4() {
    assertEquals("a3b4", compress("aaabbbb"));
}

@Test
public void test_abc() {
    assertEquals("abc", compress("abc"));
}

@Test
public void test_aabccccddddddde() {
    assertEquals("a2bc4d7e", compress("aabccccddddddde"));
}

Your code passes these cases fine. But it doesn't pass this:

@Test
public void test_aabaaa() {
    assertEquals("a2ba3", compress("aabaaa"));
}

Your method returns a5b for this input. Although your specification is not 100% clear, when you talk about "compression", I think lossless compression is implied, meaning that it's possible to restore the original version from the compressed form. In your implementation this is not the case, a5b is not reversible to aabaaa.

I suspect the current behavior is not what you intended, but a bug in your code.

General coding practice issues

There are a couple of general coding practice issues with your posted code:

  • Use interface types instead of implementations in variable declarations and method signatures as much as possible: replace LinkedHashMap with Map where you can
  • Instead of iterating over the keys of a Map and then getting the values in the loop body, it's more efficient to iterate over the entries, as in that case you save a map lookup, as in an entry the value is accessible directly without lookup
  • No need to call c.toString() on a character when concatenating to a String
  • When using a StringBuilder, instead of .append(a + b), it's better to chain the calls: .append(a).append(b)
  • It's pointless to declare the keySet variable outside of the loop, when you only use it inside the loop. It's best to limit variables to their smallest scope possible.

Following these suggestions above, the compressString method can be written better and shorter:

public static String compressString(String s) {
    Map<Character, Integer> charCountMap = createCharacterCountMap(s);
    StringBuilder result = new StringBuilder();

    for (Map.Entry<Character, Integer> entry : charCountMap.entrySet()) {
        Character c = entry.getKey();
        int val = entry.getValue();
        result.append(c);
        if (val > 1) {
            result.append(val);
        }
    }
    return result.toString();
}

Suggested implementation

I recommend a different approach, without the need for a set or a map. For example this version really compresses (reversible), and passes the tests I pointed out above:

public static String compress(String input) {
    if (input.length() < 2) {
        return input;
    }

    char[] chars = input.toCharArray();
    StringBuilder builder = new StringBuilder();

    int count = 1;
    char prev = chars[0];
    for (int i = 1; i < chars.length; ++i) {
        char current = chars[i];
        if (current == prev) {
            ++count;
        } else {
            builder.append(prev);
            if (count > 1) {
                builder.append(count);
            }
            count = 1;
        }
        prev = current;
    }
    builder.append(prev);
    if (count > 1) {
        builder.append(count);
    }
    return builder.toString();
}
\$\endgroup\$
1
\$\begingroup\$

Ensure that you maintain the order of the characters and not mix the count of same characters at different indexes i.e

bbaabb = b2a2b2 and != a2b4 // no reordering
aabbaa =a2b2a2 !=a4b2       // no combining same characters irrespective of indices.

The LinkedHashMap is wrongly doing. The compression should also be decompressed to the original string.

One loop to traverse the characters,
That loop to compress the string,
That loop to get it all done,
and zero in on to the answer ring :P

Test cases:

  1. null = null
  2. "" = ""
  3. abcd = abcd
  4. aabcd = a2bcd
  5. abcdd = abcd2
  6. aabbbccccddddd = a2b3c4d5
  7. aabbaabb = a2b2a2b2
  8. a = a
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.