Home » Technical Interview Questions » String Interview Questions » Run length encoding

# Run length encoding

## Run length encoding on the given input string.

### Example

Input string is : “aaaabbbddddzz”

Output string : a4b3d4z2

Here, a is coming 4 times, b is coming 3 times, d is coming 4 times and z is coming 2 times.

Time complexity: O(n)

## Algorithm

1. Pick the first character from the input string.

2. Append the picked character to the output string.

3. Count the number of subsequent occurrences of the same picked character.

4. Append the count into output string.

5. Pick the next character and repeat the above steps again.

6. Do this until the end of string is reached.

7. print the final output string.

## C++ Program

```#include <bits/stdc++.h>

using namespace std;

#define N 50//Max r_len

//functiont to encode
char *encode(char *string)
{
int r_len;
char count[N];
int length = strlen(string);
//max size will be 2*length + 1
char *result = (char *)malloc(sizeof(char)*(length*2 + 1));
int i, j = 0, k;
/* traverse the input string one by one */
for(i = 0; i < length; i++)
{
//First occurence of char
result[j++] = string[i];
//Find the number of occurences
r_len = 1;
while(i + 1 < length && string[i] == string[i+1])
{
r_len++;
i++;
}
//store it in count array
sprintf(count, "%d", r_len);
for(k = 0; *(count+k); k++, j++)
{
result[j] = count[k];//copy to destination
}
}
//Null termination
result[j] = '\0';
return result;
}
//Main function
int main()
{
char string[] = "aaaabbbddddzz";
char *result = encode(string);
cout<<"Output string:";
cout<<result;
}```