Palindrome Permutation

Given a string, determine if a permutation of the string could form a palindrome.

For example, "code"-> False,"aab"-> True,"carerac"-> True.

Hint:

1. Consider the palindromes of odd vs even length. What difference do you notice?

2. Count the frequency of each character.

3. If each character occurs even number of times, then it must be a palindrome. How about character which occurs odd number of times?

class Solution(object):
    def canPermutePalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        if not s:
            return False

        dict = {}

        for idx, elem in enumerate(s):
            if elem not in dict:
                dict[elem] = 1
            else:
                dict[elem] += 1

        if len(s) % 2 == 0: # even length string
            for elem, cnt in dict.iteritems():
                if cnt % 2 != 0:
                    return False
        else: # odd length string; will allow only one char to be odd
            cntOddElem = 0
            for elem, cnt in dict.iteritems():
                if cnt % 2 != 0:
                    cntOddElem += 1

            if cntOddElem > 1:
                return False

        return True

class Solution(object):
    def canPermutePalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        if not s:
            return False

        dict = {}
        for idx, elem in enumerate(s):
           if elem not in dict:
                dict[elem] = 1
            else:
                dict[elem] += 1

        cntOddElem = 0
        for elem, cnt in dict.iteritems():
            if cnt % 2 == 1 and len(s) % 2 == 0: # even number of elements in string
                return False
            elif cnt % 2 == 1 and len(s) % 2 == 1: # odd number of elements in string
                cntOddElem += 1

        if cntOddElem:
            return (cntOddElem == 1)

        return True