# CTCI Chapter 1 : Palindrome Permutation

Below is my code for the problem 1.4 in CTCI. I would like a review of my code and if my approach to the problem is correct.

Problem Statement: Palindrome Permutation: 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 forwards and backwards. A permutation is a rearrangement of letters. The palindrome does not need to be limited to just dictionary words.

EXAMPLE

Input: Tact Coa

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

My Solution (Python):

def checkPalindromeAndPermutation(inputstr):
lengthOfInputString = len(inputstr)
counterforodd = 0
actualCharactersInInput = 0
inputstr = inputstr.lower()
hashTable = dict()

for i in inputstr:
if i != " ":
hashTable[i] = hashTable.get(i, 0) + 1
actualCharactersInInput = actualCharactersInInput + 1
print(hashTable)

for item in hashTable:
# if input has even length, but each character's frequency is not even, then it's not a plaindrome
if actualCharactersInInput % 2 == 0 and hashTable[item] % 2 != 0:
return False
# if input has odd length, but more than one character's frequency is greater than 1 , then it's not a plaindrome
if actualCharactersInInput % 2 == 1 and hashTable[item] % 2 == 1:
counterforodd = counterforodd + 1
if counterforodd > 1:
return False
return True

print("Answer : " , checkPalindromeAndPermutation("abc bac"))

• The logic can be simplified. You only need to verify that at most 1 character has an odd count. – Florian F Aug 12 '19 at 11:28

Nice implementation.

Here are a couple suggestions

### collections.defaultdict

Intead of hashTable[i] = hashTable.get(i, 0) + 1, use collections.defaultdict

charcount = defaultdict(int)

for char in inputStr:
charcount[char] += 1
actualCharactersInInput = len(inputStr) - charcount[' ']


### collections.Counter

Or better yet, use a Counter:

charcount = collections.Counter(inputStr)
actualCharactersInInput = len(inputStr) - charcount[' ']


### other

if actualCharactersInInput % 2:
# odd number of chars
return sum(count%2 for count in charcount.values()) == 1
else:
# even number of chars
return not any(count % 2 for count in charcount.values())

• Thank you so much, I learned something new today :) – Manas Tripathi Aug 12 '19 at 2:21
• You can "smarten" the final check. If the length is odd there must be 1 character with an odd frequency. If the length is even there must be 0 characters with an odd frequency. Change not any(count % 2 for count in charcount.values()) to sum(count%2 for count in charcount.values()) == 0. Then the check is one line return sum(count%2 for count in charcount.values()) == actualCharactersInInput % 2 – spyr03 Aug 12 '19 at 14:19
• @spyr03, I thought of that too, but opted to use not any(...) because it would stop when it found the first odd count rather than sum the entire list. Probably a case of premature optimization. – RootTwo Aug 12 '19 at 18:38

This looks correct! Here are my thoughts on the code:

• Per PEP-8, use snake_case for variable names and PascalCase for class names.
• Use Python builtins. Python makes frequency counting effortless using collections.Counter.
• Unused variable: lengthOfInputString. A static code analysis tool like a linter can spot this.
• Avoid variable names like hashMap. Something like freq_count, seen or char_count is clearer.
• Avoid using i as the loop block variable in for i in enumerable:. Reserve i for index variables and prefer something like c or elem that describes the variable more accurately.
• The function name, checkPalindromeAndPermutation, doesn't accurately describe what the function does, long as it is. I prefer is_palindrome_permutation or palindrome_permutation.
• Remove all print statements from your functions to avoid side effects.
• While I'm not a fan of inline comments, the comments in this program explain the logic nicely (typo and horizontal scrolling aside). Consider moving them to the function docstring, though, which summarizes the entire function neatly and gets out of the way of the code.
• actualCharactersInInput can be replaced with len(s) assuming you don't mind stripping whitespace beforehand. Having a separate cached variable for holding len() is generally poor practice because the overhead of the function call is worth it to improve readability and reduce the risk of subtle bugs (len() and cached value going out of sync).
• Use foo += 1 instead of foo = foo + 1 to increment an integer.
• Branching inside the for loop doesn't make much sense since the length of actualCharactersInInput is fixed. It makes more sense to pick a branch and stick to it as a human might do naturally if performing this task by hand.

for item in hashTable:
if actualCharactersInInput % 2 == 0 and hashTable[item] % 2 != 0:
...
elif actualCharactersInInput % 2 == 1 and hashTable[item] % 2 == 1:
#^^^ we can use elif since the conditional is disjoint
...


try:

if actualCharactersInInput % 2 == 0:
for item in hashTable:
if hashTable[item] % 2 != 0:
...
else:
for item in hashTable:
if hashTable[item] % 2 == 1:
...


Luckily, branch prediction will make the performance impact negligible even if we apply the conditional inside the loop, so this is mostly about reducing cognitive load on the programmer and isn't a hard-line rule.

Here's a possible re-write:

from collections import Counter

def permuted_palindrome(s):
s = "".join(s.lower().split())
odds = [x for x in Counter(s).values() if x % 2]

if len(s) % 2 == 0:
return len(odds) < 1

return len(odds) < 2


This can cause a performance drop because of a lack of early return option. Benchmark the impact and make a call of performance vs brevity based on your use case.

I recommend validating correctness on any algorithm that's easily written using a clear-cut brute force method:

from collections import Counter
from itertools import permutations
from random import randint as rnd

def permuted_palindrome(s):
'''
Determines if a string is a permuted palindrome.
A string is a permuted palindrome if:
1. the string is of odd length and has 1 or fewer
characters with an odd number of occurrences.
- or -
2. the string is of even length and has no
characters with an odd number of occurrences.

>>> permuted_palindrome("aaa")
True
>>> permuted_palindrome("aaab")
False
>>> permuted_palindrome("aaaab")
True
>>> permuted_palindrome("aaaabc")
False
>>> permuted_palindrome("aaaabcc")
True
'''
s = "".join(s.lower().split())
odds = [x for x in Counter(s).values() if x % 2]

if len(s) % 2 == 0:
return len(odds) < 1

return len(odds) < 2

def brute_permuted_palindrome(s):
return any(x == x[::-1] for x in permutations("".join(s.lower().split())))

if __name__ == "__main__":
tests = 1000
passes = 0

for x in range(tests):
s = "".join(chr(rnd(65, 70)) for x in range(rnd(1, 10)))

if brute_permuted_palindrome(s) == permuted_palindrome(s):
passes += 1

print(f"passed {passes}/{tests} tests")


Randomization doesn't guarantee perfect coverage, but it's an easy way to be pretty certain your code works and can often catch edge cases that might be overlooked in enumeration (best to do both).

This snippet also shows how you might include a full docstring with doctests and uses the if __name__ == "__main__": guard which makes your module easily importable.

• Waow, Thank you for a detailed explanation. This is very helpful. – Manas Tripathi Aug 12 '19 at 2:21
• Why  s = "".join(s.lower().split()) instead of s.lower() or s.casefold(). And if you do odds = sum(x % 2 for x in Counter(s).values()),you don't need the len, and can do return odds < 1 + (len(s) % 2) – Maarten Fabré Aug 12 '19 at 8:48
• You can reduce the return logic to return len(odds) == len(s) % 2. Even length strings can have no odds, while odd length strings can have one. – spyr03 Aug 12 '19 at 14:22
• Thanks for the feedback. s = "".join(s.lower().split()) removes whitespace and lowers the string. After removing whitespace, the rest of the logic is much cleaner, and this handles more than just spaces. I kept len over sum because sum seemed to obfuscate the logic a bit. return len(odds) == len(s) % 2 seems reasonable but I think going terser at this point has diminishing returns. – ggorlen Aug 12 '19 at 14:51

Revised from my C# version Using a set instead of a dictionary or hashtable uses less space We casefold to ignore case sensitivity and then by sorting this we can try to fail out early. If we have any more than 2 odd letters (which will happen any time we check a third unique char) then we fail out. But we don't want to fail when checking the second member, because it could possibly be removed. If we didn't fail early we still want to make sure we have at most one odd letter. Therefore the final boolean comparison returns appropriately.

    def isPermutedPalindrome(input_string):
if (len(input_string) < 2):
return True
input_string = sorted(input_string.casefold())

char_set = set()
for letter in input_string:
if letter == ' ':
continue
if letter in char_set:
char_set.remove(letter)
else:

• In python, a set would be a more natural datastructure for this char_list than a list. And the letter is ' ' only works because CPython interns a number of strings that occur a lot. letter == ' ' is more universally correct – Maarten Fabré Aug 16 '19 at 7:17