Teaching Kids Programming – Palindrome Permutation Algorithm

Teaching Kids Programming: Videos on Data Structures and Algorithms

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

Example 1:
Input: “code”
Output: false

Example 2:
Input: “aab”
Output: true

Example 3:
Input: “carerac”
Output: true

Hints:
Consider the palindromes of odd vs even length. What difference do you notice?
Count the frequency of each character.
If each character occurs even number of times, then it must be a palindrome. How about character which occurs odd number of times?

Palindrome Permutation Algorithm by using Counter (Hash Table) Object

In Python, we can use the collections.Counter to count the frequencies for each item in the list. First, we count this by converting the string into a list. Then, if we check each frequency and find more than 1 character has odd number of frequencies, then it can’t be possible to permutate the string to make a palindrome.

1
2
3
4
5
6
7
8
9
10

class Solution:
    def canPermutePalindrome(self, s: str) -> bool:
        d = Counter(list(s))
        odd = 0
        for i in d.keys():
            if (d[i] & 1) == 1:
                odd += 1
                if odd > 1:
                    return False
        return True

class Solution:
    def canPermutePalindrome(self, s: str) -> bool:
        d = Counter(list(s))
        odd = 0
        for i in d.keys():
            if (d[i] & 1) == 1:
                odd += 1
                if odd > 1:
                    return False
        return True

The time and space complexity is both O(N) where N is the number of characters in the string.

–EOF (The Ultimate Computing & Technology Blog)