Queries to calculate difference between the frequencies of the most and least occurring characters in specified substring | Java 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 ; Driver Code ; Given String ; Given queries ; Function Call
import java . util . * ; class GFG { static void update ( int BIT [ ] [ ] , int idx , int i , int val ) { while ( i < 10005 ) { BIT [ idx ] [ i ] += val ; i = i + ( i & ( - i ) ) ; } } static int query ( int BIT [ ] [ ] , int idx , int i ) { int ans = 0 ; while ( i > 0 ) { ans += BIT [ idx ] [ i ] ; i = i - ( i & ( - i ) ) ; } return ans ; } static void maxDiffFreq ( String s , int [ ] [ ] queries ) { int [ ] [ ] BIT = new int [ 26 ] [ 10005 ] ; int n = s . length ( ) ; for ( int i = 0 ; i < n ; i ++ ) { update ( BIT , s . charAt ( i ) - ' a ' , i + 1 , 1 ) ; } int Q = queries . length ; for ( int i = 0 ; i < Q ; ++ i ) { int mx = 0 ; int mn = Integer . MAX_VALUE ; int l = queries [ i ] [ 0 ] ; int r = queries [ i ] [ 1 ] ; for ( int j = 0 ; j < 26 ; j ++ ) { int p = query ( BIT , j , r ) ; int q = query ( BIT , j , l - 1 ) ; mx = Math . max ( mx , p - q ) ; if ( p > 0 ) { mn = Math . min ( mn , p - q ) ; } } System . out . print ( mx - mn + "NEW_LINE"); } } public static void main ( String [ ] args ) { String S = " abaabac " ; int [ ] [ ] queries = { { 2 , 6 } , { 1 , 7 } } ; maxDiffFreq ( S , queries ) ; } }