current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 3 down vote favorite

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()){
            seq[c]++;
        }
        for (char c : str.toCharArray()){
            if(seq[c]>0){
                strComp.append(c).append(seq[c]);
                seq[c]=0;//so that it does not enter , when char occurs again
            }
        }

        if(str.length()<strComp.length()){
            return str;
        }
        return strComp.toString();

    }
    public static void main(String[] args) {
        CompressChar ch = new CompressChar();
        System.out.println(ch.compressString("abbcdrfac"));
    }
}
share|improve this question
    
What you can and cannot do after receiving answers – Jamal♦ Oct 30 '14 at 23:07
    
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 – Rohit Katyal Oct 30 '14 at 23:37
    
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. – Origineil Oct 31 '14 at 15:45
up vote 8 down vote accepted

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:

a11b5c6d1r1f1

when it should produce:

a5b5c1d1r1f1a6c5

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.

share|improve this answer
    
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? – Hoppe Dec 24 '15 at 14:41
up vote 2 down vote

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
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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