Anagram of a Palindrome

Given a string s consisting of lowercase letters, determine whether any permutation of s can form a palindrome.

Recall that a string is a palindrome if it reads the same backwards and forwards. A necessary and sufficient condition for a string to be rearranged into a palindrome is that the number of characters with an odd frequency is at most one. Mathematically, if count(c) is the frequency of character c in the string, the string can be rearranged into a palindrome if and only if

$$\sum_{c\in S}\left(count(c)\bmod 2\right) \le 1$$

For example, the string "carrace" can be rearranged into "racecar", which is a palindrome, while "leetcode" cannot form any palindrome permutation.

inputFormat

The input consists of a single line containing a string s composed only of lowercase letters (a-z). The string may be empty.

Note: The input is provided via stdin.

outputFormat

Output a single line: True if the string can be rearranged into a palindrome, or False otherwise. The output should be printed to stdout without extra spaces or newlines.

carrace

True