





'''simple docstring'''


from collections import Counter
from timeit import timeit


def 	__a(SCREAMING_SNAKE_CASE_  :					str = ""		,       ):



    '''simple docstring'''





    return sum(c % 2 for c in Counter(input_str.replace(" "		,       ""    ).lower()    ).values()    ) < 2


def 	__a(SCREAMING_SNAKE_CASE_  :					str = ""    ):



    '''simple docstring'''





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

    for character in lower_case_input_str:
        _lowerCAmelCase				=      character_freq_dict.get(a_		,       0    ) + 1
    _lowerCAmelCase				=      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 	__a(SCREAMING_SNAKE_CASE_  :					str = ""    ):



    '''simple docstring'''





    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	 =   input(
           "Enter string to determine if it can be rearranged as a palindrome or not: "
       ).strip()
       benchmark(check_str)
       _SCREAMING_SNAKE_CASE	 =   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'''


def 	__a(SCREAMING_SNAKE_CASE_  :					list[int]		,       SCREAMING_SNAKE_CASE_  :					list[int]		,       SCREAMING_SNAKE_CASE_  :					int    ):



    '''simple docstring'''





    return not any(
        neighbour == 1 and colored_vertices[i] == color
        for i, neighbour in enumerate(SCREAMING_SNAKE_CASE_    )    )


def 	__a(SCREAMING_SNAKE_CASE_  :					list[list[int]]		,       SCREAMING_SNAKE_CASE_  :					int		,       SCREAMING_SNAKE_CASE_  :					list[int]		,       SCREAMING_SNAKE_CASE_  :					int    ):



    '''simple docstring'''





    if index == len(SCREAMING_SNAKE_CASE_    ):
        return True

    # Recursive Step
    for i in range(SCREAMING_SNAKE_CASE_    ):
        if valid_coloring(graph[index]		,       SCREAMING_SNAKE_CASE_		,       SCREAMING_SNAKE_CASE_    ):
            # Color current vertex
            _lowerCAmelCase				=      i
            # Validate coloring
            if util_color(SCREAMING_SNAKE_CASE_		,       SCREAMING_SNAKE_CASE_		,       SCREAMING_SNAKE_CASE_		,       index + 1    ):
                return True
            # Backtrack
            _lowerCAmelCase				=      -1
    return False





def 	__a(SCREAMING_SNAKE_CASE_  :					list[list[int]]		,       SCREAMING_SNAKE_CASE_  :					int    ):



    '''simple docstring'''





    _lowerCAmelCase				=      [-1] * len(SCREAMING_SNAKE_CASE_    )

    if util_color(SCREAMING_SNAKE_CASE_		,       SCREAMING_SNAKE_CASE_		,       SCREAMING_SNAKE_CASE_		,       0    ):
        return colored_vertices

    return []


