Run Length Encoding
20 January, 2014 - 6 min read
Given an input string, write a function that returns the Run Length Encoded string for the input string.
For example, if the input string is “wwwwaaadexxxxxx”, then the function should return “w4a3d1e1x6″.
Algorithm:
a) Pick the first character from source string.
b) Append the picked character to the destination string.
c) Count the number of subsequent occurrences of the picked character and append the count to destination string.
d) Pick the next character and repeat steps b) c) and d) if end of string is NOT reached.
1: #include<stdio.h>
2: #include<string.h>
3: #include<stdlib.h>
4: #include <conio.h>
5: #include <iostream>
6:
7: using namespace std ;
8:
9: #define MAX_RLEN 50
10:
11: /* Returns the Run Length Encoded string for the
12: source string src */
13: char *encode(char *src)
14: {
15: int rLen;
16: char count[MAX_RLEN];
17: int len = strlen(src);
18:
19: /* If all characters in the source string are different,
20: then size of destination string would be twice of input string.
21: For example if the src is "abcd", then dest would be "a1b1c1d1"
22: For other inputs, size would be less than twice. */
23: char *dest = new char [sizeof(char)*(len*2 + 1)];
24:
25: int i, j = 0, k;
26:
27: /* traverse the input string one by one */
28: for(i = 0; i < len; i++)
29: {
30:
31: /* Copy the first occurrence of the new character */
32: dest[j++] = src[i];
33:
34: /* Count the number of occurrences of the new character */
35: rLen = 1;
36: while(i + 1 < len && src[i] == src[i+1])
37: {
38: rLen++;
39: i++;
40: }
41:
42: /* Store rLen in a character array count[] */
43: sprintf(count, "%d", rLen);
44:
45: /* Copy the count[] to destination */
46: for(k = 0; *(count+k); k++, j++)
47: {
48: dest[j] = count[k];
49: }
50:
51: }
52:
53: /*terminate the destination string */
54: dest[j] = '';
55: return dest;
56: }
57:
58: /*driver program to test above function */
59: int main()
60: {
61: cout << "Enter the Streing ===> " ;
62: char * str = new char [ sizeof(char) * MAX_RLEN ] ;
63: cin >> str ;
64: char *res = encode(str);
65: cout << res ;
66:
67: getch();
68: return 0 ;
69: }
Time Complexity: O(n)