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 [Last updated : March 20, 2023]

Problem Description

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

Solution of Run-length encoding

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