Optimal Compression (inspired by UVa #909)
===
To simplify, we will use the 26 upper case letters intead of the full ASCII
code.
We want to compress a string using run-length encoding. We would like to encode
a string such as "AAAABBB" as "4A 3B", but remember, numbers and spaces are not
part of our character set anymore. "DA CB" would do, interpreting odd letters as
their numeric position in the alphabet.
In this system, "ABCD" would compress to "AA AB AC AD" (with spaces stripped
out), even though that's even longer than the original. That's not good.
Here is a compression scheme which copes well with non-repeated data:
"AAAA BBB CCC" --compress--> "4A 3C 3C"
"ABCD EEE FGH" --compress--> "-4ABCD 3E -3FGH"
Negative repetition counts are not repetition counts at all, but rather indicate
how many subsequent letters should be interpreted as having a count of 1.
Again, we will need to use letters to represent numbers, including a few
negative ones:
A= 1 B= 2 C= 3 D= 4 E= 5 F= 6 G= 7 H= 8 I= 9 J=10 K=11 L=12 M=13
N=-13 O=-12 P=-11 Q=-10 R=-9 S=-8 T=-7 U=-6 V=-5 W=-4 X=-3 Y=-2 Z=-1
A compressed string can be decompressed using the following algorithm:
while more letters remain:
letter <- read next letter
count <- number represented by [letter]
if [count] is positive:
letter <- read next letter
repeat [count] times:
output [letter]
else [count] is negative:
count <- absolute value of [count]
repeat [count] times:
letter <- read next letter
output [letter]
You may think that the corresponding compression algorithm should be
straightforward, but consider the two following compressions of the string
"ABCDDEFG":
"-3ABC 2D -3EFG" aka "XABCBDXEFG" (10 letters)
"-8ABCDDEFG" aka "SABCDDEFG" (9 letters)
The example above shows that compressing using a positive count as often as
possible is not an optimal strategy. Can you find an optimal one? Given a string
of upper case letters, find an optimally-compressed string of upper case
letters, and output its length.
Hint! Use dynamic programming.