Index of character depending on frequency count in string | C ++ implementation of the approach ; Function to perform the queries ; L [ i ] [ j ] stores the largest i such that ith character appears exactly jth times in str [ 0. . . i ] ; F [ i ] [ j ] stores the smallest i such that ith character appears exactly jth times in str [ 0. . . i ] ; To store the frequency of each of the character of str ; Current character of str ; Update its frequency ; For every lowercase character of the English alphabet ; If it is equal to the character under consideration then update L [ ] [ ] and R [ ] [ ] as it is cnt [ j ] th occurrence of character k ; Only update L [ ] [ ] as k has not been occurred so only index has to be incremented ; Perform the queries ; Type 1 query ; Type 2 query ; Driver code ; Queries ; Perform the queries
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int MAX = 26 ; void performQueries ( string str , int q , int type [ ] , char ch [ ] , int freq [ ] ) { int n = str . length ( ) ; int L [ MAX ] [ n ] ; int F [ MAX ] [ n ] ; int cnt [ MAX ] = { 0 } ; for ( int i = 0 ; i < n ; i ++ ) { int k = str [ i ] - ' a ' ; cnt [ k ] ++ ; for ( int j = 0 ; j < MAX ; j ++ ) { if ( k == j ) { L [ j ] [ cnt [ j ] ] = i ; F [ j ] [ cnt [ j ] ] = i ; } else L [ j ] [ cnt [ j ] ] = L [ j ] [ cnt [ j ] ] + 1 ; } } for ( int i = 0 ; i < q ; i ++ ) { if ( type [ i ] == 1 ) { cout << L [ ch [ i ] - ' a ' ] [ freq [ i ] ] ; } else { cout << F [ ch [ i ] - ' a ' ] [ freq [ i ] ] ; } cout << " STRNEWLINE " ; } } int main ( ) { string str = " geeksforgeeks " ; int type [ ] = { 1 , 2 } ; char ch [ ] = { ' e ' , ' k ' } ; int freq [ ] = { 2 , 2 } ; int q = sizeof ( type ) / sizeof ( int ) ; performQueries ( str , q , type , ch , freq ) ; return 0 ; }