Queries to calculate difference between the frequencies of the most and least occurring characters in specified substring | 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
function update ( BIT , idx , i , val ) { while ( i < 10005 ) { BIT [ idx ] [ i ] += val ; i = i + ( i & ( - i ) ) ; } } function query ( BIT , idx , i ) { let ans = 0 ; while ( i > 0 ) { ans += BIT [ idx ] [ i ] ; i = i - ( i & ( - i ) ) ; } return ans ; } function maxDiffFreq ( s , queries ) { let BIT = new Array ( 26 ) ; for ( let i = 0 ; i < 26 ; i ++ ) { BIT [ i ] = new Array ( 10005 ) ; for ( let j = 0 ; j < 10005 ; j ++ ) { BIT [ i ] [ j ] = 0 ; } } let n = s . length ; for ( let i = 0 ; i < n ; i ++ ) { update ( BIT , s [ i ] . charCodeAt ( 0 ) - ' ' . charCodeAt ( 0 ) , i + 1 , 1 ) ; } let Q = queries . length ; for ( let i = 0 ; i < Q ; ++ i ) { let mx = 0 ; let mn = Number . MAX_VALUE ; let l = queries [ i ] [ 0 ] ; let r = queries [ i ] [ 1 ] ; for ( let j = 0 ; j < 26 ; j ++ ) { let p = query ( BIT , j , r ) ; let q = query ( BIT , j , l - 1 ) ; mx = Math . max ( mx , p - q ) ; if ( p > 0 ) { mn = Math . min ( mn , p - q ) ; } } document . write ( mx - mn + " " ) ; } } let S = " " ; let queries = [ [ 2 , 6 ] , [ 1 , 7 ] ] ; maxDiffFreq ( S , queries ) ;