Queries to count characters having odd frequency in a range [ L , R ] | Java Program to implement the above problem ; Function to print the number of characters having odd frequencies for each query ; A function to construct the arr [ ] and prefix [ ] ; Stores array length ; Stores the unique powers of 2 associated to each character ; Prefix array to store the XOR values from array elements ; Driver Code
import java . util . * ; class GFG { static class pair { int first , second ; public pair ( int first , int second ) { this . first = first ; this . second = second ; } } static void queryResult ( int prefix [ ] , pair Q ) { int l = Q . first ; int r = Q . second ; if ( l == 0 ) { int xorval = prefix [ r ] ; System . out . print ( Integer . bitCount ( xorval ) + "NEW_LINE"); } else { int xorval = prefix [ r ] ^ prefix [ l - 1 ] ; System . out . print ( Integer . bitCount ( xorval ) + "NEW_LINE"); } } static void calculateCount ( String S , pair Q [ ] , int m ) { int n = S . length ( ) ; int [ ] arr = new int [ n ] ; for ( int i = 0 ; i < n ; i ++ ) { arr [ i ] = ( 1 << ( S . charAt ( i ) - ' a ' ) ) ; } int [ ] prefix = new int [ n ] ; int x = 0 ; for ( int i = 0 ; i < n ; i ++ ) { x ^= arr [ i ] ; prefix [ i ] = x ; } for ( int i = 0 ; i < m ; i ++ ) { queryResult ( prefix , Q [ i ] ) ; } } public static void main ( String [ ] args ) { String S = " geeksforgeeks " ; pair Q [ ] = { new pair ( 2 , 4 ) , new pair ( 0 , 3 ) , new pair ( 0 , 12 ) } ; calculateCount ( S , Q , 3 ) ; } }