Test if the string is a permuted palindrome (problem 1.4. from "Cracking the Coding Interview")

is_permuted_palindrome.py

def is_permuted_palindrome(s):
    """Checks if the string is a permuted version of a palindrome
    
    Upper case do not matter, spaces can be ignored.
    
    Example:
    
    "cat cat" -> Yes (palindrome: "cat tac")
    "cat do"  -> No
    
    Algorithm #1: 
    
    1. Make a dictionary of symbols (symbol:occ_cnt);
    2. Iterate over string and count occurences. 
        Time complexity: n O(1) dictionary insertions => O(n);
        Space complexity: O(n) for dictionary.
    3. Check that no more than 1 symbol have odd number of occurences. Time complexity: O(n)
    
    Overall complexity: space O(n), time O(n)
    
    ! Correction: this is not particularly True, since the number of letters in alpahber is constant! (So Algorithm would 
    have O(1) space complexity as well, and Algo#2 do not make any sense!).
    
    Algorithm #2 (not relevant for finite alphabet):
    
    1. Sort string with some inplace algorithm. Example: heap sort. Space: O(1), time: O(n*log(n))
    2. Iterate over sorted string: iterate until we find more than 2 symbols that have odd number of occurences
    
    Overall complexity: space O(1), time O(n log(n))
    
    Corner cases:
    0. Handling spaces? Special symbols, etc.? Upper\lower case?
    1. Null string;
    2. 1 character;
    3. Check that it works for both odd and even;
    4. Very large string that do not fit in memory? Can we apply map-reduce strategy here?
    
    """
    
    #algo 1 implementation
    
    occ_dict = {} # symbol occurency dictionary
    
    for x in s:
        x = x.lower()
        if x==' ':
            continue
        if x in occ_dict:
            occ_dict[x] += 1
        else:
            occ_dict[x] = 1
    
    odd_cnt = 0
    for x in occ_dict.keys():
        if occ_dict[x] % 2 !=0:
            odd_cnt += 1
    
    if odd_cnt>1:
        is_perm_pal = False
    else:
        is_perm_pal = True
    
    return is_perm_pal
    

# Demo
print("Test is_permuted_palindrome function")
test_strings = ['', ' ', 'Tact Coa', 'abd']
for s in test_strings:
    print("\'%s\' : %r" %(s, is_permuted_palindrome(s)))