Run length encoding

Run-length encoding (RLE) is a very simple form of data compression in which runs of data (that is, sequences in which the same data value occurs in many consecutive data elements) are stored as a single data value and count, rather than as the original run. Count of 1 is not indicated. Write a program to find RLE of given string.

Eg.
input = "aabbbcddeef" RLE = "a2b3cd2e2f"
input = "aaabbcddeeeef" RLE = "a3b2cd2e4f"

Solution :

We simply use a switch while checking each character in input and count them if equal and print the count if count is greater than one.

Complexity :

• Time : O(N)
• Space : O(1)

Code :
void rle_encode(char[] input, int N, char[] output){

int index = 0, count = 1;
char last = input[0];

for(int i=1; input[i]; i++){

if(last == input[i]){

count++;

}
else {

output[index++] = last;
if(count > 1){

output[index++] = count + '0';
count = 1;

}
last = input[i];

}

}

output[index++] = last;
if(count > 1){

output[index++] = count + '0';

}

}