# 266. Palindrome Permutation

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
``````

Hint:

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

``````class Solution {
public:
bool canPermutePalindrome(string s) {
unordered_map<char, int> m;
int cnt = 0;
for (auto a : s) ++m[a];
for (auto a : m) {
if (a.second % 2 == 1) ++cnt;
}
return cnt == 0 || (s.size() % 2 == 1 && cnt == 1);
}
};
``````

``````class Solution {
public:
bool canPermutePalindrome(string s) {
unordered_set<char> st;
for (auto a : s) {
if (!st.count(a)) st.insert(a);
else st.erase(a);
}
return st.empty() || st.size() == 1;
}
};
``````

``````class Solution {
public:
bool canPermutePalindrome(string s) {
bitset<256> b;
for (auto a : s) {
b.flip(a);
}
return b.count() < 2;
}
};
``````

Longest Palindromic Substring

Valid Anagram

Palindrome Permutation II

Longest Palindromic Substring

https://leetcode.com/problems/palindrome-permutation/

https://leetcode.com/problems/palindrome-permutation/discuss/69574/1-4-lines-Python-Ruby-C%2B%2B-C-Java

https://leetcode.com/problems/palindrome-permutation/discuss/69582/Java-solution-wSet-one-pass-without-counters.

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation