Part $1$: Programming $(70$ points$)$

$1.(25$ points$)$ A palindrome is a string that reads the same backward as forward. For example,

$$madam$$ and $$test tset$$ are palindromes but $$banana$$ is not. Given a string s$,$ write a function

canFormPalindrome$($s$)$ that tests whether the letters in s can be permuted to form a palindrome.

Note:

$$ Your algorithm must use hashing $($or dictionary in Python$).$

$$ The time complexity is O$($n$),$ where n is the length of the input string.

$$ Assume an empty string is a palindrome.

Examples:

$$ canFormPalindrome$($aamdm$)$ should return True

Explanation: $$aamdm$$ can be permuated to $$madam$,$ which is a palindrome.

$$ canFormPalindrome$($abbddaaa$)$ should return True

Explanation: $$abbddaaa$$ can be permuated to $$aabddbaa$,$ which is a palindrome.

$$ canFormPalindrome$($abcc$)$ should return False