Check if a string is a permutation of a palindrome using Python

Question

This is a solution to exercise 1.4 from Cracking the Coding Interview written using Python 3.

Given a string, write a function to check if it is a permutation of a palindrome.

Example: 'Tact Coa'

Output: True (permutations: "taco cat", "atco cta", etc.)

I wanted to get feedback on making my code clearer and more pythonic. I believe my code has time complexity \$O(n)\$ and space complexity \$ O(n)\$ is that correct? If so, is there any way to improve on either the space or time complexity?

from collections import Counter
def is_palindrome_permutation(data: str) -> bool:
 """Given a string, check if it is a permutation of a palindrome."""
 data = data.lower().replace(' ', '')
 num_odd = sum(1 for char, freq in Counter(data).items() if char != ' ' and freq % 2 == 1)
# Check for two types of palindromes , 1) Odd Length (e.g. abc cba) 2) Even Length (e.g. abc d cba)
 if num_odd == 1 and len(data) % 2 == 1 or num_odd == 0 and len(data) % 2 == 0:
 return True
 else:
 return False

Test

datum = 'Tac4t co@A @4'

print(is_palindrome_permutation(datum))

Result

True

Test

datum = 'Tac4t co@A @4s'

print(is_palindrome_permutation(datum))

Result

False

Answer 1

Some suggestions:

1. You strip out spaces, then on the next line check if each character is a space. The second part is redundant.
2. The only possible values for freq % 2 are 0 and 1, so num_odd = sum(1 for char, freq in Counter(data).items() if char != ' ' and freq % 2 == 1) can be simplified as num_odd = sum(freq % 2 for Counter(data).values())
3. If num_odd is 0, then there must be an even number of elements. If num_odd is 1, then there must be an odd number of elements. So really all you care about is if there is more than 1 odd count.
4. You can return the results of expressions directly. So something like return x < y is simpler than using an if test and manually returning True or False depending on the outcome.
5. I would put the replace first since that reduces the number of characters that lower has to operate over (although this is probably a silly negligible micro optimization).

So the code can be simplified to:

from collections import Counter
def is_palindrome_permutation(data: str) -> bool:
 """Given a string, check if it is a permutation of a palindrome."""
 data = data.replace(' ', '').lower()
 return sum(freq%2 for freq in Counter(data).values()) < 2

One more thing you could do is put the Counter on the first line. I think this hurts readability a bit, but does mean that your modified data can be garbage collected right away. There is no point doing this with .values(), though, since this is just a view into the Counter object, so the Counter object has to be kept in memory.

from collections import Counter
def is_palindrome_permutation(data: str) -> bool:
 """Given a string, check if it is a permutation of a palindrome."""
 data = Counter(data.replace(' ', '').lower())
 return sum(freq%2 for freq in data.values()) < 2

Answer 2

if num_odd == 1 and len(data) % 2 == 1 or num_odd == 0 and len(data) % 2 == 0:

is a long way to say

if num_odd == len(data) % 2:

---

if condition:
 return True
else:
 return False

is a long way to say

return condition

---

You don't need to check that char != ' ': you already filtered them out one line above. In any case, stick to a Single Responsibility Principle. If you count odd occurrences, just count them.

• Average: do you recommend changing num_odd to odd_occurences?