Longest Substring that can be made a palindrome by swapping of characters | C ++ program for the above approach ; Function to find the Longest substring that can be made a palindrome by swapping of characters ; Initialize dp array of size 1024 ; Initializeing dp array with length of s ; Initializing mask and res ; Traverse the string ; Find the mask of the current character ; Finding the length of the longest substring in s which is a palindrome for even count ; Finding the length of the longest substring in s which is a palindrome for one odd count ; Finding maximum length of substring having one odd count ; dp [ mask ] is minimum of current i and dp [ mask ] ; Return longest length of the substring which forms a palindrome with swaps ; Driver Code ; Input String ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int longestSubstring ( string s ) { int dp [ 1024 ] ; fill ( dp , dp + 1024 , s . size ( ) ) ; int res = 0 , mask = 0 ; dp [ 0 ] = -1 ; for ( int i = 0 ; i < s . size ( ) ; ++ i ) { mask ^= 1 << ( s [ i ] - 48 ) ; res = max ( res , i - dp [ mask ] ) ; for ( int j = 0 ; j <= 9 ; ++ j ) res = max ( res , i - dp [ mask ^ ( 1 << j ) ] ) ; dp [ mask ] = min ( dp [ mask ] , i ) ; } return res ; } int main ( ) { string s = "3242415" ; cout << longestSubstring ( s ) ; return 0 ; }