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.
#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);
}
#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
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+" ");
}
}
#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]);
}
}
}