Queries for frequencies of characters in substrings | Python3 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 Code
MAX_LEN , MAX_CHAR = 1005 , 26 NEW_LINE cnt = [ [ 0 for i in range ( MAX_CHAR ) ] for j in range ( MAX_LEN ) ] NEW_LINE def preProcess ( s ) : NEW_LINE INDENT n = len ( s ) NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT cnt [ i ] [ ord ( s [ i ] ) - ord ( ' a ' ) ] += 1 NEW_LINE DEDENT for i in range ( 1 , n ) : NEW_LINE INDENT for j in range ( 0 , 26 ) : NEW_LINE INDENT cnt [ i ] [ j ] += cnt [ i - 1 ] [ j ] NEW_LINE DEDENT DEDENT DEDENT def findCharFreq ( l , r , c ) : NEW_LINE INDENT return ( cnt [ r ] [ ord ( c ) - 97 ] - cnt [ l - 1 ] [ ord ( c ) - 97 ] ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT s = " geeksforgeeks " NEW_LINE Q = 4 NEW_LINE preProcess ( s ) NEW_LINE print ( findCharFreq ( 0 , 5 , ' e ' ) ) NEW_LINE print ( findCharFreq ( 2 , 6 , ' f ' ) ) NEW_LINE print ( findCharFreq ( 4 , 7 , ' m ' ) ) NEW_LINE print ( findCharFreq ( 0 , 12 , ' e ' ) ) NEW_LINE DEDENT