Maximum length palindrome that can be created with characters in range L and R | Java implementation of the approach ; Function to return the length of the longest palindrome that can be formed using the characters in the range [ l , r ] ; 0 - based indexing ; Marks if there is an odd frequency character ; Length of the longest palindrome possible from characters in range ; Traverse for all characters and count their frequencies ; Find the frequency in range 1 - r ; Exclude the frequencies in range 1 - ( l - 1 ) ; If frequency is odd , then add 1 less than the original frequency to make it even ; Else completely add if even ; If any odd frequency character is present then add 1 ; Function to pre - calculate the frequencies of the characters to reduce complexity ; Iterate and increase the count ; Create a prefix type array ; Driver code ; Pre - calculate prefix array ; Perform queries
class GFG { static int N = 4 ; static int performQueries ( int l , int r , int prefix [ ] [ ] ) { l -- ; r -- ; boolean flag = false ; int count = 0 ; for ( int i = 0 ; i < 26 ; i ++ ) { int cnt = prefix [ r ] [ i ] ; if ( l > 0 ) cnt -= prefix [ l - 1 ] [ i ] ; if ( cnt % 2 == 1 ) { flag = true ; count += cnt - 1 ; } else count += cnt ; } if ( flag ) count += 1 ; return count ; } static void preCalculate ( String s , int prefix [ ] [ ] ) { int n = s . length ( ) ; for ( int i = 0 ; i < n ; i ++ ) { prefix [ i ] [ s . charAt ( i ) - ' a ' ] ++ ; } for ( int i = 1 ; i < n ; i ++ ) { for ( int j = 0 ; j < 26 ; j ++ ) prefix [ i ] [ j ] += prefix [ i - 1 ] [ j ] ; } } public static void main ( String args [ ] ) { String s = " amim " ; int prefix [ ] [ ] = new int [ N ] [ 26 ] ; preCalculate ( s , prefix ) ; int queries [ ] [ ] = { { 1 , 4 } , { 3 , 4 } } ; int q = queries . length ; for ( int i = 0 ; i < q ; i ++ ) { System . out . println ( performQueries ( queries [ i ] [ 0 ] , queries [ i ] [ 1 ] , prefix ) ) ; } } }