How to do run length encoding?

Question

I have a long string for example it could be "aaaaaabbccc". Need to represent it as "a6b2c3". What's the best way to do this ? I could do this in linear time by comparing characters and incrementing counts and then replacing the counts in the array, using two indexes in one pass. Can you guys think of a better way than this? Are any of the encoding techniques going to work here ?

Answer 1

The common solution for this is RLE - Run-length encoding, the Wikipedia article has sample implementation code.

Answer 2

I think you're asking, "Is there a better than linear way to do run-length encoding"? If so, the answer is no.

Answer 3

I don't think there is a faster way to solve it.

Informally you can think that a sub-linear complexity implies to do less comparisons that the number of the characters in the string you want to compress. But with a number of comparisons such small you can't be sure of some character, you can't know what they contain because you don't have enough information.. this means that you can't obtain a loseless compression.