Longest substring whose characters can be rearranged to form a Palindrome | C ++ program for the above approach ; Function to get the length of longest substring whose characters can be arranged to form a palindromic string ; To keep track of the last index of each xor ; Initialize answer with 0 ; Now iterate through each character of the string ; Convert the character from [ a , z ] to [ 0 , 25 ] ; Turn the temp - th bit on if character occurs odd number of times and turn off the temp - th bit off if the character occurs ever number of times ; If a mask is present in the index Therefore a palindrome is found from index [ mask ] to i ; If x is not found then add its position in the index dict . ; Check for the palindrome of odd length ; We cancel the occurrence of a character if it occurs odd number times ; Driver code ; Given String ; Length of given string ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int longestSubstring ( string s , int n ) { map < int , int > index ; int answer = 0 ; int mask = 0 ; index [ mask ] = -1 ; for ( int i = 0 ; i < n ; i ++ ) { int temp = ( int ) s [ i ] - 97 ; mask ^= ( 1 << temp ) ; if ( index [ mask ] ) { answer = max ( answer , i - index [ mask ] ) ; } else index [ mask ] = i ; for ( int j = 0 ; j < 26 ; j ++ ) { int mask2 = mask ^ ( 1 << j ) ; if ( index [ mask2 ] ) { answer = max ( answer , i - index [ mask2 ] ) ; } } } return answer ; } int main ( ) { string s = " adbabd " ; int n = s . size ( ) ; cout << ( longestSubstring ( s , n ) ) ; }