Perform basic string compression using the counts of repeated characters

Question

I managed to implement this question from Cracking the Coding Interview:

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.

Can anyone offer feedback on my code?

public static String countRepeatedChars(String str){
    int initialLength = str.length();
    char[] chars = str.toCharArray();
    int occurances = 0;
    String compressedString = "";
    char currentChar = chars[0];

    for(int i = 0; i < initialLength; i++){
        char c  = chars[i];
        if(currentChar == c && i + 1 <= initialLength){
            occurances++;
        }

        else if (currentChar != c || i + 1  > initialLength){

            compressedString += currentChar + String.valueOf(occurances);
            currentChar = chars[i];
            occurances = 1;
        }

        if(i + 1 >=  initialLength){
            compressedString += currentChar + String.valueOf(occurances);

        }
    }
    if(compressedString.length() < initialLength){
         return compressedString;
    }
    return str;
}

Answer 1

Interviewing techniques and design decisions

If you were asked a question like this in an interview, always ask your interviewer for clarification. Not only does it avoid misunderstandings, it also demonstrates your ability to identify corner cases. You can score points before writing a single line of code!

In this case, the question I would ask is: how should a streak of 10 or more identical characters be encoded? An encoded string that always alternates character, count, character, count etc. would be easy to decode. However, a two-digit count would break the pattern and make it harder to decode. Indeed, the interpretation could even be ambiguous. For example, does the encoded string a101c9 mean aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaccccccccc or a0ccccccccc? I would argue that it should be interpreted as the latter, since

• otherwise there would be no good way to compress a0ccccccccc, and
• we could preserve the nice character-count-character-count alternation, which is a useful property for decoding.

If we make that design decision, then, it seems to follow that a string consisting of a repeated 101 times followed by c repeated 9 times would have to be encoded as a9a9a9a9a9a9a9a9a9a9a9a2c9.

That is the design decision that I would make, and I would justify it like that to my interviewer.

Critiques

• Repeated string concatenation is a no-no! In Java, strings are immutable, so every time you do + or +=, you create a new string by allocating a chunk of memory, copying the entire contents of the old string, then copying the string to be appended. Using + once or twice is fine, but never do it many times in a loop! Use a StringBuilder instead. In this case, you could also just use a char[] buffer, since you know that the buffer should never grow beyond a certain limit — the length of the input string.
• Speaking of the length limit… you only compare the length of the compressed string at the end, when you are basically already done. A smarter algorithm might be able to bail out earlier if the length is exceeded.

• You have redundant conditions:

  for(int i = 0; i < initialLength; i++){
      char c  = chars[i];
      if(currentChar == c && i + 1 <= initialLength){
          occurances++;
      }
  
      else if (currentChar != c || i + 1  > initialLength){
  

  i + 1 <= initialLength would be more idiomatically written as i < initialLength. But that is exactly the condition of the for loop itself! Therefore, the i + 1 <= initialLength test is always true, and superfluous.

  By the same reasoning, i + 1 > initialLength can never be true, and is also superfluous. The remaining else if (currentChar != c) could just be written as else.

• The special case for the loop termination is clumsy. This condition

  if(i + 1 >=  initialLength){
  

  can happen just once, at the very last iteration of the loop. You can therefore just move it out of the loop.

• What happens with degenerate input? For example, if str is an empty string, then your code would crash on char currentChar = chars[0]. By my interpretation, a zero-length input should produce an empty string as output. In fact, if you see an input of length 0, 1, or 2, you could immediately return str.

• "Occurances" should be spelled "occurrences".

Suggested solution

This code would address the concerns above. I've used just a char[] array as scratch space. By writing directly to the buffer, I've eliminated the need to write another compressedString += currentChar + String.valueOf(occurances) at the end.

JavaDoc would be a nice touch. If coding on a whiteboard, a "verbal" comment might be good enough, though.

/**
 * Performs run-length encoding on a string.  If the encoded string
 * would be longer than the input, then the input string is returned.
 * To make decoding simple and unambiguous, streaks are limited to
 * 9 characters long; longer streaks are broken up.
 */
public static String compress(String in) {
    if (in.length() < 3) return in;

    int n = in.length(), i = 0, o = 0;
    char[] out = new char[n + 1];
    out[o++] = in.charAt(0);
    out[o++] = '1';
    for (i = 1; i < n && o < n; i++) {
        if (in.charAt(i) == in.charAt(i - 1) && out[o - 1] != '9') {
            // Continued streak
            out[o - 1]++;
        } else {
            // New streak
            out[o++] = in.charAt(i);
            out[o++] = '1';
        }
    }
    return (i == n && o < n) ? new String(out, 0, o) : in;
}

Answer 2

String concatenation in a loop

String concatenation in a loop is inefficient, and a well-known rookie mistake. Use a StringBuilder instead.

Simplify implementation

The loop body has several conditions comparing i + 1 and initialLength. It would be more efficient and simpler to move the special treatment of the last character sequence out of the loop:

for(int i = 0; i < initialLength; i++){
    char c  = chars[i];
    if(currentChar == c) {
        occurances++;
    } else {
        compressedString += currentChar + String.valueOf(occurances);
        currentChar = c;
        occurances = 1;
    }
}
compressedString += currentChar + String.valueOf(occurances);

In this simpler form, notice that the loop variable i is not needed anywhere in the loop body. So now we can rewrite it as a for-each loop:

for (char c : chars) {

Naming and single responsibility principle

The method name countRepeatedChars is not really appropriate. How about compress?

More importantly, the method actually does two things: it applies a compression algorithm, and then decides to use it or not. This algorithm is also known as run-length encoding. It would be better to move the algorithm to its own method, for example named encodeRunLength, and then compress can be implemented in terms of this method + the decision what to return.

I would also rename currentChar to simply current, and occurances to simply count.