266_Palindrome Permutation

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

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

Solution

In order to be palindrome after permutation, the number of characters with odd number of occurences can't exceed 1(1 in case of odd length and 0 in case of even length)

1. Count the frequency of each letter, stored in a dictionary

2. Check if more than one frequency is odd

Time: O(n)

Space: O(1)

class Solution(object):
    def canPermutePalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        # count frequency of each letter
        dic = {}
        for l in s:
            if dic.get(l) is None:
                dic[l] = 1
            else:
                dic[l] += 1
        # compute how many of the frequencies are odd
        # if more than one, return False immediately
        module = 0
        for i in dic.values():
            module += i%2
            if module > 1:
                return False
        return True