Blog # 58 : Run Length Encoding (RLE)

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" Click here to see the solution. p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice. Courtesy: Vibhaj Remarks: No remark dude :P. Hit again for hints. Hints: This is an intelligent problem, try to solve it without a hint. Hit again for Solution 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: 1. TIme : O(N) 2. 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'; } }