Queries for frequencies of characters in substrings | CPP program to find occurrence of character in substring l to r ; To store count of all character ; To pre - process string from 0 to size of string ; Store occurrence of character i ; Store occurrence o all character upto i ; To return occurrence of character in range l to r ; Return occurrence of character from 0 to r minus its occurrence from 0 to l ; Driver program to test above functions
#include <bits/stdc++.h> NEW_LINE #define MAX_LEN  1005 NEW_LINE #define MAX_CHAR  26 NEW_LINE using namespace std ; int cnt [ MAX_LEN ] [ MAX_CHAR ] ; void preProcess ( string s ) { int n = s . length ( ) ; memset ( cnt , 0 , sizeof ( cnt ) ) ; for ( int i = 0 ; i < n ; i ++ ) cnt [ i ] [ s [ i ] - ' a ' ] ++ ; for ( int i = 1 ; i < n ; i ++ ) { for ( int j = 0 ; j < 26 ; j ++ ) cnt [ i ] [ j ] += cnt [ i - 1 ] [ j ] ; } } int findCharFreq ( int l , int r , char c ) { int count = cnt [ r ] [ c - ' a ' ] ; if ( l != 0 ) count -= cnt [ l - 1 ] [ c - ' a ' ] ; return count ; } int main ( ) { string s = " geeksforgeeks " ; int Q = 4 ; preProcess ( s ) ; cout << findCharFreq ( 0 , 5 , ' e ' ) << endl ; cout << findCharFreq ( 2 , 6 , ' f ' ) << endl ; cout << findCharFreq ( 4 , 7 , ' m ' ) << endl ; cout << findCharFreq ( 0 , 12 , ' e ' ) << endl ; return 0 ; }