Basic string compression counting repeated characters

Question

My task was to implement a method which performs basic string compression by counting sequences of repeating characters. Given "aaabbbccc" it should return "a3b3c3". I have included some sample tests I made up. Please let me know if I have missed any cases. I am looking for the fastest implementation possible with the most concise code. I'm looking to cut down on if else statements or give them simpler logic if possible.

public class StringCompression {
    public String compress(String str){
        int count = 1;
        StringBuilder builder = new StringBuilder();

        for(int i = 1; i<str.length(); i++){

            if(str.charAt(i) == str.charAt(i-1) && i < str.length()-1){
                count++;
            }
            // case when the last letter is in the sequence preceding it. Add that sequence to
            // the compressed string
            else if(i == str.length()-1 && str.charAt(i) == str.charAt(i-1)){
                count++;
                builder.append(str.charAt(i));
                builder.append(count);
            }

            // case where the last letter is NOT in the sequence preceding it. Add it to string.
            else if(i == str.length()-1 && str.charAt(i) != str.charAt(i-1)){
                builder.append(str.charAt(i-1));
                builder.append(count);
                count = 1;
                builder.append(str.charAt(i));
                builder.append(count);
            }
            else{
                // appending the character and THEN appending the count works.
                builder.append(str.charAt(i-1));
                builder.append(count);
                count = 1;
            }

        }

        str = builder.toString();
        System.out.println(str);

        return str;
    }

    public static void main(String[] args){
        StringCompression test = new StringCompression();

        test.compress("aabcccccaaa");
        test.compress("aaaaa");
        test.compress("aaaabbb");
        test.compress("aaabbbccc");
        test.compress("abc");
        test.compress("a");
        test.compress("");
    }
}

Answer 1

As @vnp said, don't print the result for "testing". Convert each statement in the main method to proper unit tests, for example:

@Test
public void test_aabcccccaaa() {
    assertEquals("a2b1c5a3", compress("aabcccccaaa"));
}

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

Once this is done, you can go ahead and safely refactor the rest of the code, having an easy way to repeat the tests.

Being aware of, and working knowledge of unit testing should definitely score you extra points in a job interview, or might be even required.

Bug

For single letter inputs, the method seems to return an empty string. That looks incorrect. Judging by that for "abc" it returns "a1b1c1", it would seem that for "a" it should return "a1" instead of an empty string

Simplify

The algorithm can be simplified to these steps:

• Loop over the characters, from the 2nd till the end
• If the current character is the same as the previous, increment the count
• If different, append the count and append the previous character
• After the end of the loop, append the count

The implementation can be something like this:

public String compress(String str) {
    if (str.isEmpty()) {
        return "";
    }

    char[] chars = str.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).append(count);
            count = 1;
        }
        prev = current;
    }
    return builder.append(prev).append(count).toString();
}

Answer 2

Order of expressions in if statement

Your code would be more readable if you would be consistent with your ordering in the if clause. You have

str.charAt(i) == str.charAt(i - 1) && i < str.length() - 1

but:

i == str.length() - 1 && str.charAt(i) == str.charAt(i - 1)

instead of:

str.charAt(i) == str.charAt(i - 1) && i == str.length() - 1

Last Loop

You have two conditions that only apply in the last loop. I would pull those out to after the loop:

public static String compress(String str) {
    int count = 1;
    StringBuilder builder = new StringBuilder();

    for (int i = 1; i < str.length() - 1; i++) {
        if (str.charAt(i) == str.charAt(i - 1)) {
            count++;
        } else {
            builder.append(str.charAt(i - 1));
            builder.append(count);
            count = 1;
        }
    }
    // special cases for last chars
    if (str.length() > 1) {
        if (str.charAt(str.length() - 1) == str.charAt(str.length() - 2)) {
            count++;
        } else {
            builder.append(str.charAt(str.length() - 2));
            builder.append(count);
            count = 1;
        }
        builder.append(str.charAt(str.length() - 1));
        builder.append(count);
    }
    return builder.toString();
}

Answer 3

• A compress method shall not print.

• Returning string doesn't look right. I'd let caller pass down anything which implements append (I am not too fluent in Java though). In any case make sure that count never exceeds 256.

• I don't see why do you need to special case i == str.length()-1.

• Passing null results in an exception. It is OK as long as compress throws.

Answer 4

We can avoid many of the references to str.charAt(i-1) by introducing a variable (mark) which points to the new character that ends a run.

Also, we can combine a couple of the conditions while boundary condition is kept in mind.

That looks like this:

public class StringCompression {
    public static String compress(String s){
        int count = 1;
        int mark=0;
        StringBuilder builder = new StringBuilder();

        for(int i = 1; i<s.length(); i++){
            if(s.charAt(i)==s.charAt(i-1)&& i<s.length()-1){
                count++;
            }
            else if(i==s.length()-1 && s.charAt(i)==s.charAt(i-1)){
                count++;
                builder.append(s.charAt(mark));
                builder.append(count);
                count=1;
                mark=i;
            }
            else{
                builder.append(s.charAt(mark));
                builder.append(count);
                count=1;
                mark=i;
            }
        }
        return builder.toString();
    }

    public static void main(String z[]){
        System.out.println(compress("aabbccddefghiiijjkaaa"));
    }
}