String Compression

Question

Implement a method to perform basic string compression using the counts of repeated characters.

For example, the string "aabcccccaaa" would become "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).

My solution is:

GitHub

public class StringCompression {

  public static String compress(String input) {
    if (input == null) {
      return null;
    }

    StringBuilder output = new StringBuilder();

    char prevChar = input.charAt(0);
    int lengthSoFar = 1;

    for (int index = 1; index < input.length(); index++) {
      char currentChar = input.charAt(index);

      if (prevChar == currentChar) {
        lengthSoFar++;
      } else {
        output.append(prevChar);
        output.append(lengthSoFar);

        // reset counters
        prevChar = currentChar;
        lengthSoFar = 1;
      }
    }
    output.append(prevChar);
    output.append(lengthSoFar);

    return output.toString().length() <= input.length() ? output.toString() : input;
  }
}

Answer 1

For input "fooo", the implementation returns "f1o3", which is the same length, and violates one of the requirements:

If the "compressed" string would not become smaller than the original string, your method should return the original string.

The fix is in the return statement: change <= to <.

---

Another corner case is when the input is empty, the statement char prevChar = input.charAt(0); will throw StringIndexOutOfBoundsException.

---

Lastly, a performance pitfall in the return statement, output.toString() creates a new string, therefore the following may result in double computation:

return output.toString().length() < input.length() ? output.toString() : input;

You could instead benefit from the length() method of StringBuilder:

return output.length() < input.length() ? output.toString() : input;

Answer 2

Generates an out of bounds exception if passed an empty (but not null) string.

The new StringBuilder() should be passed an initial size for the character buffer, to avoid continuous reallocations. Lacking any other reasonable value, I’d recommend passing in the original string length.

StringBuilder output = new StringBuilder(input.length());