$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 $\backslash ($ O$($n$)\backslash ),$ where $\backslash ($ n $\backslash )$ 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

$2.(25$ points$)$ Suppose you need to write an anonymous letter and disguise your handwriting. You decide to cut the characters you need from a book and paste the characters on a paper to form the letter. $($Note that we mean a physical book and a physical letter, not digital.$)$ Given the content of a book book and the content of the letter letter $($each is reprented as a string$),$ write a function anonymousLetter$($book$,$ letter$)$ that determines if it is possible to write the anonymous letter using the book.

Note:

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

$-$ The time complexity is $\backslash ($ O$(\backslash$max $($m$,$ n$))\backslash ),$ where $\backslash ($ m $\backslash )$ is the length of the book string and $\backslash ($ n $\backslash )$ is the length of the letter.

Examples:

$-$ Let the book be "I am a book. Not a letter." and the letter be "I am a letter." anonymousLetter$($book$,$ letter$)$ should return True.

$-$ Let the book be "I am a book. Not a letter." and the letter be "I am a letter!" anonymousLetter$($book$,$ letter$)$ should return False.

$-$ Let the book be "abcde" and the letter be "abcdef" anonymousLetter$($book$,$ letter$)$ should return False. $```$

from collections import $*$

$"""$

$1.$ Tests whether the letters in a string can be permuted to form a palindrome.

$"""$

def canFormPalindrome$($s$)$:

$"""$

$2.$ Determines if it is possible to write an anonymous letter using a book.

$"""$

def anonymousLetter$($book$,$ letter$)$:

$``````$

from hw$06$ import $*$

def check$($val$,$ expected$)$:

if val $==$ expected:

print$("$Passed$")$

else:

print$("$Failed$")$

print$("$Your output $=",$ val$)$

print$("$Expected output $=",$ expected$)$

class TestCanFormPalindrome:

def test$2($self$)$:

print$("$canFormPalindrome case $2$: s $=\text{'}$x$\text{'}(2$ point$)$:$")$

l $="$x$"$

val $=$ canFormPalindrome$($l$)$

check$($val$,$ True$)$

def test$4($self$)$:

print$("$canFormPalindrome case $4$: s $=\text{'}$xzz$\text{'}(2$ point$)$:$")$

l $="$xzz$"$

val $=$ canFormPalindrome$($l$)$

check$($val$,$ True$)$

def test$6($self$)$:

print$("$canFormPalindrome case $6$: s $=$ 'abxzzbbx' $(2$ point$)$:$")$

l $=$ "abxzzbbx"

val $=$ canFormPalindrome$($l$)$

check$($val$,$ False$)$

def test$8($self$)$:

print$("$canFormPalindrome case $8$: s $=$ 'axzzbbxa' $(2$ point$)$:$")$

l $=$ "axzzbbxa"

val $=$ canFormPalindrome$($l$)$

check$($val$,$ True$)$

def test$10($self$)$:

print$("$canFormPalindrome case $10$: s $=$

'aaabacaaadacabaaaaaaaaaadadaaaadaaaeaaaaaaaaaaa' $(2$ point$)$:$")$

l $=$ "aaabacaaadacabaaaaaaaaaadadaaaadaaaeaaaaaaaaaaa"

val $=$ canFormPalindrome$($l$)$

check$($val$,$ True$)$

test $=$ TestCanFormPalindrome$()$

test.test$2()$

test.test$4()$

test.test$6()$

test.test$8()$

test.test$10()$

$``````$

from hw$06$ import $*$

def check$($val$,$ expected$)$:

if val $==$ expected:

print$("$Passed$")$

else:

print$("$Failed$")$

print$("$Your output $=",$ val$)$

print$("$Expected output $=",$ expected$)$

class TestAnonymousLetter:

def test$2($self$)$:

print$("$anonymousLetter case $2$: book $=$ 'alsfjei', letter $=\text{'}\text{'}(2$ point$)$:$")$

b $=$ "alsfjei"

l $=""$

val $=$ anonymousLetter$($b$,$ l$)$

check$($val$,$ True$)$

def test$4($self$)$:

print$("$anonymousLetter case $4$: book $=\text{'}$xzz$\text{'},$ letter $=\text{'}$xzz$\text{'}(2$ point$)$:$")$

b $="$xzz$"$

l $="$xzz$"$

val $=$ anonymousLetter$($b$,$ l$)$

check$($val$,$ True$)$

def test$5($self$)$:

print$("$anonymousLetter case $5$: book $=\text{'}$xzz$\text{'},$ letter $=\text{'}$zxzx$\text{'}(2$ point$)$:$")$

b $="$xzz$"$

l $="$zxzx$"$

val $=$ anonymousLetter$($b$,$ l$)$

check$($val$,$ False$)$

def test$6($self$)$:

print$("$anonymousLetter case $6$: book $=$ 'febxxzz', letter $=\text{'}$zxzx$\text{'}(2$

point$)$:$")$

b $=$ "febxxzz"

l $="$zxzx$"$

val $=$ anonymousLetter$($b$,$ l$)$

check$($val$,$ True$)$

def test$9($self$)$:

print$("$anonymousLetter case $9$: book $=$ 'abxaxabbz', letter $=$ 'abxzzbbxz' $(2$

point$)$:$")$

b $=$ "abxaxabbz"

l $=$ "abxzzbbxa"

val $=$ anonymousLetter$($b$,$ l$)$

check$($val$,$ False$)$

test $=$ TestAnonymousLetter$()$

test.test$2()$

test.test$4()$

test.test$5()$

test.test$6()$

test.test$9()$

$```$