266

266. Palindrome Permutation (Easy)

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

Companies:
Facebook, Google, Microsoft

Related Topics:
Hash Table

Similar Questions:

• Longest Palindromic Substring (Medium)
• Valid Anagram (Easy)
• Palindrome Permutation II (Medium)
• Longest Palindrome (Easy)

Solution 1.

// OJ: https://leetcode.com/problems/palindrome-permutation/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    bool canPermutePalindrome(string s) {
        int cnt[26] = {}, single = 0;
        for (char c : s) cnt[c - 'a']++;
        for (int n : cnt) {
            single += n % 2;
            if (single > 1) return false;
        }
        return true;
    }
};