How to check if permutation of a string is a palindrome

Im new to python and im trying to check if any permutation of a string is a palindrome. Here is my code:

def isPal(s):
    a = set()
    for i in s:
        if i in a:
            a.remove(i)
        else:
            if (i != 'n') or (i != ' '):
                a.add(i)
    if len(a) <= 1:
        print(s + ' is a palindrome permutationn')
    else:
        print(s + ' is not a palindrome permutationn')
     print(a)

The problem I am having is that it I dont want my set to include spaces or any puncuation thats in the string. Is there any way to only check the letters? For example, the string “Mr. owl ate my Metal worm” shouldnt use the period or spaces when checking if it is a palindrome.

Answer

You can certainly check all permutations, but there is a much more efficient approach.

Note that in order for a string to be a palindrome, then every letter is mirrored around the center of the string. That means a collection of letters can form a palindrome if there is at most one letter that has an odd count.

Here is how you can implement this:

The first step is to convert the string to lower case and remove the nonalpha characters (like spaces and punctuation). We can do that by using a list comprehension to iterate over each character in the string and keep only those where str.isalpha() returns True.

myString = "Mr. owl ate my Metal worm"
alpha_chars_only = [x for x in myString.lower() if x.isalpha()]
print(alpha_chars_only)
#['m', 'r', 'o', 'w', 'l', 'a', 't', 'e', 'm', 'y', 'm', 'e', 't', 'a', 'l', 'w', 'o', 'r', 'm']

Next count each letter. You can use collections.Counter for this:

from collections import Counter 
counts = Counter(alpha_chars_only)
print(counts)
#Counter({'m': 4, 'a': 2, 'e': 2, 'l': 2, 'o': 2, 'r': 2, 't': 2, 'w': 2, 'y': 1})

Finally count the number of letters that have an odd count. If the count is 0 or 1, a palindrome must be possible.

number_of_odd = sum(1 for letter, cnt in counts.items() if cnt%2)
print(number_of_odd)
#1

Putting that all together, you can make a function:

def any_palindrome(myString):
    alpha_chars_only = [x for x in myString.lower() if x.isalpha()]
    counts = Counter(alpha_chars_only)
    number_of_odd = sum(1 for letter, cnt in counts.items() if cnt%2)
    return number_of_odd <= 1

print(any_palindrome(mystring))
#True