Check if string can be rearranged so that every Odd length Substring is Palindrome | C ++ implementation of the above approach ; Function to check is it possible to rearrange the string such that every odd length substring is palindrome ; Length of the string ; To count number of distinct character in string ; To count frequency of each character ; Inserting into set ; Incrementing the frequency ; All characters in the string are same ; There are more than 2 different character in string ; Currently there is 2 different character in string ; Get the frequencies of the characters that present in string ; Difference between their count is less than or equal to 1 ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool IsPossible ( string s ) { int n = s . length ( ) ; set < char > count ; map < char , int > map ; for ( int i = 0 ; i < n ; i ++ ) { count . insert ( s [ i ] ) ; map [ s [ i ] ] += 1 ; } if ( count . size ( ) == 1 ) { return true ; } if ( count . size ( ) > 2 ) { return false ; } auto it = count . begin ( ) ; int x = 0 , y = 0 ; x = map [ * it ] ; it ++ ; y = map [ * it ] ; if ( abs ( x - y ) <= 1 ) { return true ; } return false ; } int main ( ) { string s = " aaaddad " ; if ( IsPossible ( s ) ) cout << " YES STRNEWLINE " ; else cout << " NO STRNEWLINE " ; return 0 ; }