
from collections import Counter
from timeit import timeit



def 							lowerCamelCase_	( __UpperCamelCase = ""			,    ):
				return sum(c % 2 for c in Counter(input_str.replace(''' '''			,    ''''''  ).lower()  ).values()  ) < 2



def 							lowerCamelCase_	( __UpperCamelCase = ""  ):






				if len(a__  ) == 0:
								return True
				A_													=	input_str.replace(''' '''			,    ''''''  ).lower()
				# character_freq_dict: Stores the frequency of every character in the input string
				A_													=	{}

				for character in lower_case_input_str:
								A_													=	character_freq_dict.get(a__			,    0  ) + 1
				A_													=	0

				for character_count in character_freq_dict.values():
								if character_count % 2:
												odd_char += 1
				if odd_char > 1:
								return False
				return True



def 							lowerCamelCase_	( __UpperCamelCase = ""  ):
				print('''\nFor string = '''			,    a__			,    ''':'''  )
				print(
				    '''> can_string_be_rearranged_as_palindrome_counter()'''			,    '''\tans ='''			,    can_string_be_rearranged_as_palindrome_counter(a__  )			,    '''\ttime ='''			,    timeit(
				        '''z.can_string_be_rearranged_as_palindrome_counter(z.check_str)'''			,    setup='''import __main__ as z'''			,    )			,    '''seconds'''			,    )
				print(
				    '''> can_string_be_rearranged_as_palindrome()'''			,    '''\tans ='''			,    can_string_be_rearranged_as_palindrome(a__  )			,    '''\ttime ='''			,    timeit(
				        '''z.can_string_be_rearranged_as_palindrome(z.check_str)'''			,    setup='''import __main__ as z'''			,    )			,    '''seconds'''			,    )


if __name__ == "__main__":
						SCREAMING_SNAKE_CASE :		Dict       			=							input(
						    "Enter string to determine if it can be rearranged as a palindrome or not: "
						).strip()
						benchmark(check_str)
						SCREAMING_SNAKE_CASE :		Optional[int]       			=							can_string_be_rearranged_as_palindrome_counter(check_str)
						print(f'''{check_str} can {"" if status else "not "}be rearranged as a palindrome''')







"""simple docstring"""


from __future__ import annotations

from collections import namedtuple
from dataclasses import dataclass




@dataclass
class 						__UpperCamelCase     :
					lowercase_    :				int
					lowercase_    :				TreeNode | None      =  None
					lowercase_    :				TreeNode | None      =  None


__SCREAMING_SNAKE_CASE   =   namedtuple('CoinsDistribResult', 'moves excess')


def        UpperCAmelCase      (					a__ ):





						'''simple docstring'''






						if root is None:
												return 0

						# Validation
						def count_nodes(a__ ) -> int:
												if node is None:
																		return 0

												return count_nodes(node.left ) + count_nodes(node.right ) + 1

						def count_coins(a__ ) -> int:
												if node is None:
																		return 0

												return count_coins(node.left ) + count_coins(node.right ) + node.data

						if count_nodes(a__ ) != count_coins(a__ ):
												raise ValueError('The nodes number should be same as the number of coins' )

						# Main calculation
						def get_distrib(a__ ) -> CoinsDistribResult:

												if node is None:
																		return CoinsDistribResult(0     ,      1 )

												lowerCAmelCase	, lowerCAmelCase   :Optional[int]						=			get_distrib(node.left )
												lowerCAmelCase	, lowerCAmelCase   :str						=			get_distrib(node.right )

												lowerCAmelCase   :str						=			1 - left_distrib_excess
												lowerCAmelCase   :Optional[Any]						=			1 - right_distrib_excess

												lowerCAmelCase   :Any						=			(
												    left_distrib_moves
												    + right_distrib_moves
												    + abs(a__ )
												    + abs(a__ )
												)
												lowerCAmelCase   :Tuple						=			node.data - coins_to_left - coins_to_right

												return CoinsDistribResult(a__     ,      a__ )

						return get_distrib(a__ )[0]


if __name__ == "__main__":
		import doctest

		doctest.testmod()