Saturday, January 18, 2014

Print letters followed by their frequency (Run Length Encoding)

Given a string ,Write a program to print letter followed by it’s frequency.This is also knows as Run Length Encoding.

Example:
Input aaabcc
Output a3b1c2

Algorithm:
1.Pick the first character from the string and print it.
2.Count the number of subsequent occurrences of the picked character and then print the count.
3.Pick the next character and repeat step 2 till we reach end of the String.

#include <iostream>
#include<string>
using namespace std;
 
int main()
{
    string str = "aaabcc";
    int count=0;
    int i=0,j;
    int l = str.length();
    while(i<l)
    {
 
        cout << str[i];
                count=1;
        j=i;
        while(j+1<l && str[j+1]==str[i])
        {
            count++;
            j++;
        }
        cout << count;
        i=j+1;
    }
    return 0;
}

Time Complexity : Time complexity may look O(n^2) as there are two while loops but it’s O(n) as we visit each character once.

0 comments:

Post a Comment