11
\$\begingroup\$

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("");
    }
}
\$\endgroup\$
  • 5
    \$\begingroup\$ This compression scheme is called run-length encoding. \$\endgroup\$ – David Richerby Oct 11 '14 at 9:46
  • \$\begingroup\$ How do you cope with numeric characters in your string? Something like: "Mr. Smith lives at 1223 Hollywood Avenue". And a bit more complex: "A trillion is written out: 1000000000000" \$\endgroup\$ – Ronald Oct 11 '14 at 9:54
  • \$\begingroup\$ i discussed other considerations like repeating multi-character sequences (100010001000) with the interviewer. i did what i could with 15 minutes per problem. \$\endgroup\$ – user137717 Oct 11 '14 at 21:07
9
\$\begingroup\$

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();
}
\$\endgroup\$
  • \$\begingroup\$ are unit tests and JUnit tests the same thing? \$\endgroup\$ – user137717 Oct 11 '14 at 22:02
  • 1
    \$\begingroup\$ No. JUnit is a Java library that implements the concept of unit testing \$\endgroup\$ – janos Oct 11 '14 at 22:20
3
\$\begingroup\$

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();
}
\$\endgroup\$
2
\$\begingroup\$
  • 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.

\$\endgroup\$
  • \$\begingroup\$ I think that case is needed for the last sequence. Without it, the example would be a3b3c2 instead of a3b3c3 (I'm not saying that it is needed, but the code would need some adjustments if it is removed). \$\endgroup\$ – tim Oct 11 '14 at 9:03
  • 1
    \$\begingroup\$ please explain why the caller should be able to pass anything which implements append and why the count can never exceed 256. Do you recommend throws for any particular reason instead of an if statement or tr/catch? \$\endgroup\$ – user137717 Oct 11 '14 at 20:56
  • \$\begingroup\$ @user137717 Passing an interface adds flexibility. A count greater than 256 wouldn't fit into a byte. You'd need two bytes in the result string to represent it. The decompressor will be confused. Regarding throws, I neither recommend them nor not recommend; I want the code to be consistent. Right now it may throw, but it doesn't declare that. \$\endgroup\$ – vnp Oct 11 '14 at 22:40
  • \$\begingroup\$ @tim The code needs a lot of "adjustments". Special cases emphasize this. \$\endgroup\$ – vnp Oct 11 '14 at 22:41
  • \$\begingroup\$ @vnp "Returning string doesn't look right." What?! Guava returns strings. Apache commons returns strings. The universe basically return strings as they are by a huge margin the commonest way to represent reasonably short text in Java nowadays. If you are not fluent in Java, don't comment Java-specific issues. Edit: enter instead of shift+enter. \$\endgroup\$ – Bernardo Sulzbach Jul 30 '15 at 13:06
0
\$\begingroup\$

I simply used a variable 'mark' which points to the new character that just occurred after the sequence ends, thus reducing some string operations.

Also one 'else if' is reduced while boundary condition is kept in mind.

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"));
}

}
\$\endgroup\$
  • 1
    \$\begingroup\$ No explanation, no comment ? Do you really think it will help as a review ? this site is not code golf. \$\endgroup\$ – Tensibai Nov 13 '15 at 9:16
  • \$\begingroup\$ @Tensibai I have edited the answer, hope it helps, if not do comment here, I will explain further :) \$\endgroup\$ – Liger Nov 13 '15 at 9:21
  • \$\begingroup\$ This is a code review site, the idea is to give guidance to OP on what fails/can be improved in his code. Proposing an alternative is OK as far as it is compared to OP's code and that you explain why it is better/more efficient. \$\endgroup\$ – Tensibai Nov 13 '15 at 9:23
  • \$\begingroup\$ And please fix your indentation, prepare in your editor, copy/paste here, select the code and press ctrlk+K ore the code block button which will add 4 spaces automatically to make a code block. \$\endgroup\$ – Tensibai Nov 13 '15 at 9:24

protected by 200_success Jun 9 '16 at 9:31

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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