A jeweler is about to restring a strand of beads that were removed from an old bracelet and jumbled out of order. Every bead carries a single label — one printable character — indicating its exact color and finish, and the jeweler is free to restring the beads in any order she likes, using every bead exactly once. Before starting, she wants to know whether some ordering of these specific beads would make the finished strand a palindrome: one that reads identically whether scanned from the clasp end or from the tail end. Given the sequence of bead labels as she pulled them out of the box, decide whether at least one reordering of that exact multiset of beads forms a palindrome.
A single line containing the string s of bead labels: each character of s is a printable ASCII character (code points 33 to 126, so no spaces or other whitespace), and s has length between 1 and 100000.
Print YES if some rearrangement of the characters of s forms a palindrome, otherwise print NO.
Example 1
Input
aabb
Expected
YES
Explanation
"aabb" has two 'a' characters and two 'b' characters, both even counts, so it can be rearranged into "abba", which reads the same forwards and backwards. Answer: YES.
Example 2
Input
abc
Expected
NO
Explanation
"abc" has three distinct characters, each appearing exactly once (three odd counts). A palindrome rearrangement needs at most one character with an odd count, so no ordering of "abc" can be a palindrome. Answer: NO.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →