In-place run length decoding?

Question

Given a run length encoded string, say "A3B1C2D1E1", decode the string in-place. The answer for the encoded string is "AAABCCDE". Assume that the encoded array is large enough to accommodate the decoded string, i.e. you may assume that the array size = MAX[length(encodedstirng),length(decodedstring)].

This does not seem trivial, since merely decoding A3 as 'AAA' will lead to over-writing 'B' of the original string.

Also, one cannot assume that the decoded string is always larger than the encoded string. Eg: Encoded string - 'A1B1', Decoded string is 'AB'. Any thoughts?

And it will always be a letter-digit pair, i.e. you will not be asked to converted 0515 to 0000055555

Answer 1

If we don't already know, we should scan through first, adding up the digits, in order to calculate the length of the decoded string.

It will always be a letter-digit pair, hence you can delete the 1s from the string without any confusion.

A3B1C2D1E1

becomes

A3BC2DE

Here is some code, in C++, to remove the 1s from the string (O(n) complexity).

// remove 1s
int i = 0; // read from here
int j = 0; // write to here
while(i < str.length) {
    assert(j <= i); // optional check
    if(str[i] != '1') {
        str[j] = str[i];
        ++ j;
    }
    ++ i;
}
str.resize(j); // to discard the extra space now that we've got our shorter string

Now, this string is guaranteed to be shorter than, or the same length as, the final decoded string. We can't make that claim about the original string, but we can make it about this modified string.

(An optional, trivial, step now is to replace every 2 with the previous letter. A3BCCDE, but we don't need to do that).

Now we can start working from the end. We have already calculated the length of the decoded string, and hence we know exactly where the final character will be. We can simply copy the characters from the end of our short string to their final location.

During this copy process from right-to-left, if we come across a digit, we must make multiple copies of the letter that is just to the left of the digit. You might be worried that this might risk overwriting too much data. But we proved earlier that our encoded string, or any substring thereof, will never be longer than its corresponding decoded string; this means that there will always be enough space.