Home
Aptitude
Categories


Home » Interview coding problems/challenges

Run-length encoding (find/print frequency of letters in a string)



Here, we are going to learn how to find/print the frequency of letters in a string using run-lentgh encoding?
Submitted by Radib Kar, on November 17, 2018

Problem description

Write a program that counts frequency of each letter in the string (string consists lowercase letters only).

Solution:

Algorithm

  1. Initialize an array of 26 elements for each letter (a-z) to 0. (array[26]={0})
  2. Scan the entire string and for each string element check the letter and increase the frequency in array by using ASCII value. (array[str[i]-'a']++)
    Like in str="aaabbccccddef",
    str [3] ='b'
    Thus, and str [2]-'a'=1
    Thus it increases the frequency of 'b' by 1 (array [str [3]-'a'] turns to be array [1] ++)
  3. Finally print the letter with their respective frequencies. This is the encoded string.



C++ program to find/print frequency of letters in a string

#include <bits/stdc++.h>
using namespace std;

void freq(string s){
	//array to store frequency of 26 characters,initialized to 0
	int arr[26]={0}; 

	for(int i=0;i<s.length();i++){
		// s[i] is the ascii value of the letter at index i & 'a' 
		//also gives the ascii value of a, in this way we are 
		//checking which alphabet is at index i and increasing its frequency
		arr[s[i]-'a']++;   		
	}

	for(int i=0;i<26;i++){		
		if(arr[i]!=0)
			printf("%d%c",arr[i],'a'+i);
	}	
	
	cout<<endl;
}

int main(){
	string s;
	
	cout<<"enter string\n";
	cin>>s;
	cout<<"encoded string is : "<<endl;
	freq(s);

	return 0;
}

Output

enter string
aaaabbcccccddf
encoded string is :
4a2b5c2d1f





Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.





Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing » Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates

© https://www.includehelp.com some rights reserved.