Implement a method to perform basic string compression using the counts of repeated characters. For example, the string aabcccccaaa would become a2blc5a3. If the "compressed" string would not become smaller than the original string, your method should return the original string.

Can this be implemented in a better way performance-wise?

package string;

public class CompressChar {

    int[] seq = new int [256];

    public String compressString(String str){

        StringBuffer strComp = new StringBuffer();
        for( char c : str.toCharArray()){
        for (char c : str.toCharArray()){
                seq[c]=0;//so that it does not enter , when char occurs again

            return str;
        return strComp.toString();

    public static void main(String[] args) {
        CompressChar ch = new CompressChar();
  • \$\begingroup\$ I have revised the code, rooting out the errors ,do you think i can optimize i further , posting the revised code on gist.github.com/RohitK09/f1fd72da23449364e369 \$\endgroup\$ Commented Oct 30, 2014 at 23:37
  • \$\begingroup\$ Generally you'll want to keep any post related content encapsulated here, thus you'll want to add the revised code to the end of the original post. In regards to extraneous code, you can easily get rid of the temp variables in the else block. Additionally, get rid of the wasted char[] initialization by assigning str.toCharArray() straight to strArr. \$\endgroup\$
    – Origineil
    Commented Oct 31, 2014 at 15:45

2 Answers 2


Your solution here is wrong, it produces incorrect results when it compresses chars that are in two different places in the string:

For the input: aaaaabbbbbcdrfaaaaaaccccc your program produces:


when it should produce:


Because the a and c repeat in two different places, you include them all in the first count.

Since this is homework, writing out the full solution would be counter-productive, but, if you have:

StringBuilder sb = new StringBuilder();

and two variables to contain the previous char and the previous char count, you could just go through each character in the string, if it's the same as the previous char, you increment the count. If it's different, you add the previous char and it's count to the StringBuilder, and reset the previous and count to 1.

Then, when your loop is done, if the StringBuilder is smaller than the input, return the StringBuilder version.

This type of compression is called 'run length encoding' by the way.

  • \$\begingroup\$ I received this as an interview question, and internet searches show that it may be in a book about code interviews as well. posting the full solution would be helpful on code review. Should I post a separate question? \$\endgroup\$
    – Hoppe
    Commented Dec 24, 2015 at 14:41

Use StringBuilder instead of StringBuffer because it's faster whereas synchronization is not required.

There is no reason for the array seq which is a temporary array to be a field. Declare it local to the compressString method instead.

When you call toCharArray() it allocates a new char[] initialized to the content of the string, and happens every time you call it. You can store into an array variable to avoid that.

char[] charArray = str.toCharArray()
for(char c: charArray){
// reuse the same array again

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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