Same solution can be used to inplace run length encoding, the key is to always ensure the converted string must be either shorter or longer than original one.
During encode, first convert A to A1, so the length of new string is sure to be longer, we can do this from end of string or List<char>. then convert AAA to A3, the length of new string is sure to be shorter.
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.
During encode, first convert A to A1, so the length of new string is sure to be longer, we can do this from end of string or List<char>. then convert AAA to A3, the length of new string is sure to be shorter.
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
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.
Read full article from c - In-place run length decoding? - Stack Overflow