266.Palindrome Permutation

Tags: [chars_count], [count], [map], [palindrome]

Com: {g}

Hard: [#]

Link: https://leetcode.com/problems/palindrome-permutation/\#/description

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

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

Solution: Map

class Solution(object):
    def canPermutePalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        if not s or len(s) == 1:
            return True

        chars_counts = collections.defaultdict(int)
        for c in s:
            chars_counts[c] += 1

        odd_frequency_char_counter = 0
        for c in chars_counts:
            if chars_counts[c] % 2 == 1:
                odd_frequency_char_counter += 1

            if odd_frequency_char_counter > 1:
                return False

        return True

Note:

• Time complexity = O(n), n is the length of the given string.