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.
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.
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