Maximum length palindrome that can be created with characters in range L and R | Python3 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
N = 4 NEW_LINE def performQueries ( l , r , prefix ) : NEW_LINE INDENT l -= 1 NEW_LINE r -= 1 NEW_LINE flag = False NEW_LINE count = 0 NEW_LINE for i in range ( 26 ) : NEW_LINE INDENT cnt = prefix [ r ] [ i ] NEW_LINE if ( l > 0 ) : NEW_LINE INDENT cnt -= prefix [ l - 1 ] [ i ] NEW_LINE DEDENT if ( cnt % 2 == 1 ) : NEW_LINE INDENT flag = True NEW_LINE count += cnt - 1 NEW_LINE DEDENT else : NEW_LINE INDENT count += cnt NEW_LINE DEDENT DEDENT if ( flag ) : NEW_LINE INDENT count += 1 NEW_LINE DEDENT return count NEW_LINE DEDENT def preCalculate ( s , prefix ) : NEW_LINE INDENT n = len ( s ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT prefix [ i ] [ ord ( s [ i ] ) - ord ( ' a ' ) ] += 1 NEW_LINE DEDENT for i in range ( 1 , n ) : NEW_LINE INDENT for j in range ( 26 ) : NEW_LINE INDENT prefix [ i ] [ j ] += prefix [ i - 1 ] [ j ] NEW_LINE DEDENT DEDENT DEDENT s = " amim " NEW_LINE prefix = [ [ 0 for i in range ( 26 ) ] for i in range ( N ) ] NEW_LINE preCalculate ( s , prefix ) NEW_LINE queries = [ [ 1 , 4 ] , [ 3 , 4 ] ] NEW_LINE q = len ( queries ) NEW_LINE for i in range ( q ) : NEW_LINE INDENT print ( performQueries ( queries [ i ] [ 0 ] , queries [ i ] [ 1 ] , prefix ) ) NEW_LINE DEDENT