Menu Close

C++ – Return frequencies of characters in substrings

In this tutorial, We are going to learn how to get or return frequencies of characters in substrings in o(1) in go golang.

Inputs:

  • input string from user
  • left side index
  • right side index
  • character to be searched for frequency

Logic:

  • In matrix, We will store occurrence of characters frequencies. 
  • Return occurrence of character from 0 to r minus its occurrence from 0 to l

Example:

arr[] = "techieindoor"

left index: 3
right index: 11

character to be searched for frequency: o

Output: 2

Code:

// CPP program to find occurrence
// of character in substring l to r
#include <string>
#include<iostream>
#define MAX_LEN 1005
#define MAX_CHAR 26

using namespace std;

// To store count of all character
int cnt[MAX_LEN][MAX_CHAR];

// To pre-procees string from
// 0 to size of string
void preProcess(string s)
{
    int n = (int)s.length();

    // Initializing cnt with 0
    memset(cnt, 0, sizeof(cnt));

    // Store occurrence of
    // character i
    for (int i = 0; i < n; i++)
        cnt[i][s[i] - 'a']++;

    // Store occurrence o
    // all character upto i
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 26; j++)
            cnt[i][j] += cnt[i - 1][j];
    }
}
// To return occurrence of
// character in range l to r
int findCharFreq(int l, int r, char c)
{
    // Return occurrence of character
    // from 0 to r minus its
    // occurrence from 0 to l
    return cnt[r][c-'a'] - cnt[l - 1][c-'a'];
}

// Driver program to test above functions
int main()
{
    string s;
    int q;
    cout<<"Enter the string:  ";
    cin>>s;
    cout<<"\nEnter the number of queries:  ";
    cin>>q;
   
    preProcess(s);

    for(int i = 0; i < q; i++) {
        int l, r;
        char ch;
        cout<<"\Enter left side index: ";
        cin>>l;
        cout<<"\Enter right side index: ";
        cin>>r;
        cout<<"\Enter character to be searched for frequency:  ";
        cin>>ch;
        cout << findCharFreq(l, r, ch) << endl;
    }
    return 0;
}
Enter the string:  techieindoor
Enter the number of queries: 2
ter left side index: 3
ter right side index: 11
ter character to be searched for frequency: o
2
ter left side index: 0
ter right side index: 8
ter character to be searched for frequency: i
2

To learn more about golang, Please refer given below link:

https://www.techieindoor.com/go-lang-tutorial/

References:

https://en.wikipedia.org/wiki/C%2B%2B
Posted in C++

2 Comments

Leave a Reply

Your email address will not be published.

Contact Us