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;
}

Try It

 

Translate »