How to Check Any String is Palindrome from Its Permutation?

Given any string (assume both lowercase or uppercase letters), check if a permutation of the string could form a palindrome.

For example, canPermutePalindrome(“aab”) = true while canPermutePalindrome(“ab”) = false.

A Palindrome is a string that its reverse is exactly the same. In A Palindrome, each character can only appear in even number of times e.g. abba or one letter appears the odd number of times e.g. aba. Therefore, the solution is to count the appearances of each character and if there is more than 1 characters that appear odd numbers of times..

Using Hash Table

We use a hash table (or we can create a static array e.g. int[128]) to record the counts, then we can do this with two passes O(n). The second pass check the count and return true if we find more than 1 letters appear odd number of times.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    bool canPermutePalindrome(string s) {
        unordered_map<char, int> count;
        for (const auto &n: s) {
            if (count.find(n) == count.end()) {
                count[n] = 1;
            } else {
                count[n] ++;
            }
        }
        int j = 0;
        for (auto i = count.begin(); i != count.end(); ++ i) {
            if ((i->second % 2) == 1) {
                j ++;
                if (j > 1) { // more than 1 letters appear odd number of times
                    return false;
                }
            }
        }
        return true;
    }
};

class Solution {
public:
    bool canPermutePalindrome(string s) {
        unordered_map<char, int> count;
        for (const auto &n: s) {
            if (count.find(n) == count.end()) {
                count[n] = 1;
            } else {
                count[n] ++;
            }
        }
        int j = 0;
        for (auto i = count.begin(); i != count.end(); ++ i) {
            if ((i->second % 2) == 1) {
                j ++;
                if (j > 1) { // more than 1 letters appear odd number of times
                    return false;
                }
            }
        }
        return true;
    }
};

Using Set

Using set could simplify the implementation. The odd number of times, we insert into the set, the even number of times, we remove it from the set. When iteration finishes, the size of the set is equal to the number of characters that appear the odd number of times.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
public:
    bool canPermutePalindrome(string s) {
        unordered_set<char> cache;
        for (const auto &n: s) {
            if (cache.count(n)) {
                cache.erase(n);
            } else {
                cache.insert(n);
            }
        }
        return cache.size() <= 1;
    }
};

class Solution {
public:
    bool canPermutePalindrome(string s) {
        unordered_set<char> cache;
        for (const auto &n: s) {
            if (cache.count(n)) {
                cache.erase(n);
            } else {
                cache.insert(n);
            }
        }
        return cache.size() <= 1;
    }
};

The runtime complexity is O(n) and the space complexity is also O(n) – the usage of unordered_set.

–EOF (The Ultimate Computing & Technology Blog) —