Valid Palindrome

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​‌‌​​​​‌​​‌‌‌​​​​​‌‌‌​​​​‌‌​​‌​‌​​‌‌​‌‌​​​‌‌​​​​​​‌‌​​​‌​‌‌​​​​‌​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​​​​​‌‌​​‌‌​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​ Alphanumeric characters include letters (a-z, A-Z) and digits (0-9).

Given a string S, determine if it is a palindrome. Output YES if it is a palindrome, or NO otherwise.

---

Input Format

• A single line containing the string S (1 ≤ length of S ≤ 100,000).

---

Output Format

• Print YES if ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​‌‌​​​​‌​​‌‌‌​​​​​‌‌‌​​​​‌‌​​‌​‌​​‌‌​‌‌​​​‌‌​​​​​​‌‌​​​‌​‌‌​​​​‌​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​​​​​‌‌​​‌‌​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​S is a valid palindrome, or NO otherwise.

---

Example 1

Input:

A man, a plan, a canal: Panama

Output:

YES

Explanation: After removing non-alphanumeric characters and converting to lowercase, the string becomes "amanaplanacanalpanama", which reads the same forwards and backwards.

---

Example 2

​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​‌‌​​​​‌​​‌‌‌​​​​​‌‌‌​​​​‌‌​​‌​‌​​‌‌​‌‌​​​‌‌​​​​​​‌‌​​​‌​‌‌​​​​‌​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​​​​​‌‌​​‌‌​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​Input:

race a car

Output:

NO

Explanation: After cleaning, the string is "raceacar", which is not a palindrome. ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​‌‌​​​​‌​​‌‌‌​​​​​‌‌‌​​​​‌‌​​‌​‌​​‌‌​‌‌​​​‌‌​​​​​​‌‌​​​‌​‌‌​​​​‌​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​​​​​‌‌​​‌‌​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​

race a car

NO

A man, a plan, a canal: Panama

YES