Queries to calculate difference between the frequencies of the most and least occurring characters in specified substring | Python3 program for the above approach ; Function to update frequency of a character in Fenwick tree ; Update frequency of ( idx + ' a ' ) ; Update i ; Function to find the frequency of a character ( idx + ' a ' ) in range [ 1 , i ] ; Stores frequency of character , ( idx + ' a ' ) in range [ 1 , i ] ; Update ans ; Update i ; Function to find difference between maximum and minimum frequency of a character in given range ; BIT [ i ] [ j ] : Stores frequency of ( i + ' a ' ) If j is a power of 2 , then it stores the frequency ( i + ' a ' ) of from [ 1 ] [ j ] ; Stores length of String ; Iterate over the characters of the String ; Update the frequency of s [ i ] in fenwick tree ; Stores count of queries ; Iterate over all the queries ; Stores maximum frequency of a character in range [ l , r ] ; Stores minimum frequency of a character in range [ l , r ] ; Iterate over all possible characters ; Stores frequency of ( j + ' a ' ) in range [ 1 , r ] ; Stores frequency of ( j + ' a ' ) in range [ 1 , l - 1 ] ; Update mx ; If a character ( i + ' a ' ) present in range [ l , r ] ; Update mn ; Print the difference between max and min freq ; Given String ; Given queries ; Function Call
import sys NEW_LINE def update ( BIT , idx , i , val ) : NEW_LINE INDENT while ( i < 10005 ) : NEW_LINE BIT [ idx ] [ i ] += val NEW_LINE i = i + ( i & ( - i ) ) NEW_LINE DEDENT def query ( BIT , idx , i ) : NEW_LINE INDENT ans = 0 NEW_LINE while ( i > 0 ) : NEW_LINE ans += BIT [ idx ] [ i ] NEW_LINE i = i - ( i & ( - i ) ) NEW_LINE return ans NEW_LINE DEDENT def maxDiffFreq ( s , queries ) : NEW_LINE INDENT BIT = [ [ 0 for i in range ( 10005 ) ] for j in range ( 26 ) ] NEW_LINE n = len ( s ) NEW_LINE for i in range ( n ) : NEW_LINE update ( BIT , ord ( s [ i ] ) - ord ( ' a ' ) , i + 1 , 1 ) NEW_LINE Q = len ( queries ) NEW_LINE for i in range ( Q ) : NEW_LINE mx = 0 NEW_LINE mn = sys . maxsize NEW_LINE l = queries [ i ] [ 0 ] NEW_LINE r = queries [ i ] [ 1 ] NEW_LINE for j in range ( 26 ) : NEW_LINE INDENT p = query ( BIT , j , r ) NEW_LINE q = query ( BIT , j , l - 1 ) NEW_LINE mx = max ( mx , p - q ) NEW_LINE if ( p > 0 ) : NEW_LINE mn = min ( mn , p - q ) NEW_LINE DEDENT print ( mx - mn ) NEW_LINE DEDENT S = " abaabac " NEW_LINE queries = [ [ 2 , 6 ] , [ 1 , 7 ] ] NEW_LINE maxDiffFreq ( S , queries ) NEW_LINE