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.

4 Thoughts on “Print letters followed by their frequency (Run Length Encoding)

  1. #include
    #include
    #include
    int main()
    {
    char str[100];
    int i,count=1;
    gets(str);
    for(i=0;i<strlen(str);i++)
    {
    if(str[i]==str[i+1])
    count++;
    else
    {
    printf(" %c %d ",str[i],count);
    count=1;
    }
    }

    return(0);
    }

  2. #include
    #include

    using namespace std;

    int main(){
    string str = “aaabcc”;

    map dict;

    for(unsigned int i=0; i<str.length(); i++){
    dict[str.at(i)] += 1;
    }

    map::iterator iter;
    for(iter = dict.begin(); iter!=dict.end(); iter++){
    cout<first<second;
    }
    }

    a3b1c2

  3. Tarun on June 27, 2015 at 7:01 pm said:

    public class RunLengthEncoding {

    public static void main(String[] args) {
    String str = “aaaaaabbbbbccccdddd”;
    int i,count = 1;
    for(i=1;i<str.length();i++)
    {
    if(str.charAt(i-1) == str.charAt(i))
    {

    count++;
    }
    else
    {
    System.out.print(str.charAt(i-1)+""+count+" ");
    count=1;
    }

    }
    System.out.println(str.charAt(i-1)+""+count+" ");
    }

    }

  4. Chellapandi Arumugam on July 30, 2015 at 6:01 pm said:

    #include
    #include
    int main(){
    int hash[256]={0},i;
    char arr[1000];
    gets(arr);
    for(i=0;i<strlen(arr);i++){
    hash[arr[i]]++;
    }
    for(i=0;i1){
    printf(“%c%d”,i,hash[i]);
    }
    }
    }

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation