Palindrome Permutation

Problem

Given a string s, return true if a permutation of the string could form a *palindrome* and false otherwise.

Constraints

• 1 <= s.length <= 5000
• s consists of only lowercase English letters.

Solution

The problem Palindrome Permutation can be solved by counting the number of appearances for each English characters in a given string and then checking the number of characters that appeared odd number of times. If a length of a string is odd, then the permutation can form a palindrome if and only if there is a single character that appears odd number of times. If a length of a string is even, then all characters should appear even number of times for the permutation to form a palindrome. Although the problem can be solved by considering each cases, it can be simplified once more. If there is a character α that appears odd number of times in a string with even length, then there must be at least one other character β that also appears odd number of times for the length to become even. In other words, number of characters that appear odd number of times in a string with even length is always even. This implies that if a permutation of the string with even length cannot form a palindrome, then there are at least 2 characters that appear odd number of times. Therefore, instead of considering the length of a string, it can be said that if the number of characters that appear odd number of times in a string is either 0 or 1, then the permutation of the string could form a palindrome.

Implementation

class Solution
{
  private:
    int count[26];

  public:
    bool canPermutePalindrome(string s)
    {
        for (int i = 0; i < s.length(); i++)
            count[s[i] - 'a']++;

        int odd = 0;
        for (int i = 0; i < 26; i++)
            odd += count[i] % 2;

        return odd <= 1;
    }
};