Permutes Palindrome

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 backwards and forwards. You can ignore casing and non-letter characters.

Solution 1

One way to solve this problem is to create a supplemental array to represent the frequency of letters. Each letter in the alphabet is represented in the supplemental array, for example the letter B is the second element of the array.

def char_frequency_table(input_string):
    chars = list(input_string)

    freq_table = [0]*26

    for char in chars:
        if not char.isalpha():
            continue

        i = ord(char) - ord('a')
        freq_table[i] += 1

    return freq_table

Using the frequency table, we can identify palindromes. Palindromes with an even number of letters will have only even frequencies, and palindromes with an odd number of letters will have even frequencies for all but one letter, which will have an odd frequency.

def permutes_palindrome(input_string):
    freqs = char_frequency_table(input_string)

    total = 0
    num_odd = 0

    for freq in freqs:
        total += freq
        if(freq % 2 > 0):
            num_odd += 1

    if(total % 2 > 0) and (num_odd > 1):
        return False
    elif(total % 2 == 0) and (num_odd > 0):
        return False
    else:
        return True

This solution takes time \(O(n)\).