Palindrome Permutation

CountingHash TableString

Given a string, write a function to check if it is a permutation of a palindrome. A palindrome is a word or phrase that is the same forwards and backwards. A permutation is a rearrangement of letters. The palindrome does not need to be limited to just dictionary words.

Example 1

Input

[
  "Tact Coa"
]

Output

True

Explanation. The input string 'Tact Coa' can be rearranged to form 'taco cat', which is a palindrome.

Example 2

Input

[
  "aabb"
]

Output

True

Explanation. The input string 'aabb' can be rearranged to form 'abba' or 'baab', both of which are palindromes.

Example 3

Input

[
  "race a car"
]

Output

False

Explanation. There is no possible rearrangement of 'race a car' that would result in a palindrome.

Example 4

Input

[
  " "
]

Output

True

Explanation. A single whitespace or an empty string is considered a palindrome.

Follow-up: Can you improve your solution to run in O(n) time complexity?

Constraints:

Consider only alphanumeric characters and ignore case sensitivity.

Accepted: 1/2
Acceptance Rate: 50.0%
Views: 2