Index of character depending on frequency count in string | Python3 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
import numpy as np NEW_LINE MAX = 26 ; NEW_LINE def performQueries ( string , q , type_arr , ch , freq ) : NEW_LINE INDENT n = len ( string ) ; NEW_LINE L = np . zeros ( ( MAX , n ) ) ; NEW_LINE F = np . zeros ( ( MAX , n ) ) ; NEW_LINE cnt = [ 0 ] * MAX ; NEW_LINE for i in range ( n ) : NEW_LINE INDENT k = ord ( string [ i ] ) - ord ( ' a ' ) ; NEW_LINE cnt [ k ] += 1 ; NEW_LINE for j in range ( MAX ) : NEW_LINE INDENT if ( k == j ) : NEW_LINE INDENT L [ j ] [ cnt [ j ] ] = i ; NEW_LINE F [ j ] [ cnt [ j ] ] = i ; NEW_LINE DEDENT else : NEW_LINE INDENT L [ j ] [ cnt [ j ] ] = L [ j ] [ cnt [ j ] ] + 1 ; NEW_LINE DEDENT DEDENT DEDENT for i in range ( q ) : NEW_LINE INDENT if ( type_arr [ i ] == 1 ) : NEW_LINE INDENT print ( L [ ord ( ch [ i ] ) - ord ( ' a ' ) ] [ freq [ i ] ] , end = " " ) ; NEW_LINE DEDENT else : NEW_LINE INDENT print ( F [ ord ( ch [ i ] ) - ord ( ' a ' ) ] [ freq [ i ] ] , end = " " ) ; NEW_LINE DEDENT print ( ) NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT string = " geeksforgeeks " ; NEW_LINE type_arr = [ 1 , 2 ] ; NEW_LINE ch = [ ' e ' , ' k ' ] ; NEW_LINE freq = [ 2 , 2 ] ; NEW_LINE q = len ( type_arr ) ; NEW_LINE performQueries ( string , q , type_arr , ch , freq ) ; NEW_LINE DEDENT