How to compress a string

Question

I had this question in one of my interviews:

Given a string how would you compress it?

Example input is not in the form of aabbccdd but like abcdgehrk. i.e. all chars in the string are different.(Note:Run Length Encoding wont work ,as it was one of the solutions which I gave but he said string does not have any repetitive characters)

I gave the following two solutions but he did not accept them:

1) HashCode cannot be a solution as it will store numbers
2) Can't store in binary as its not human readable format

Can anyone please suggest what could be another solution for this problem?

Answer 1

Given that the examiner required that the compressed string is human-readable, one solution is Run-Length Encoding.

aabbccdd would therefore be compressed as 2a2b2c2d, and abcdgehrk as 1a1b1c1d1g1e1h1r1k.

Note that the output string in these special examples are not shorter than the original string, but it's a property of all lossless compression algorithms that they cannot guarantee compression for any input dataset.