Check if string can be rearranged so that every Odd length Substring is Palindrome | 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
def IsPossible ( s ) : NEW_LINE INDENT n = len ( s ) ; NEW_LINE count = set ( ) ; NEW_LINE map = dict . fromkeys ( s , 0 ) ; NEW_LINE for i in range ( n ) : NEW_LINE INDENT count . add ( s [ i ] ) ; NEW_LINE map [ s [ i ] ] += 1 ; NEW_LINE DEDENT if ( len ( count ) == 1 ) : NEW_LINE INDENT return True ; NEW_LINE DEDENT if ( len ( count ) > 2 ) : NEW_LINE INDENT return False ; NEW_LINE DEDENT j = 0 NEW_LINE it = list ( count ) [ j ] ; NEW_LINE x = 0 ; y = 0 ; NEW_LINE x = map [ it ] ; NEW_LINE j += 1 NEW_LINE it = list ( count ) [ j ] ; NEW_LINE y = map [ it ] ; NEW_LINE if ( abs ( x - y ) <= 1 ) : NEW_LINE INDENT return True ; NEW_LINE DEDENT return False ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT s = " aaaddad " ; NEW_LINE if ( IsPossible ( s ) ) : NEW_LINE INDENT print ( " YES " ) ; NEW_LINE DEDENT else : NEW_LINE INDENT print ( " NO " ) ; NEW_LINE DEDENT DEDENT