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)
// OJ: https://leetcode.com/problems/palindrome-permutation/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
bool canPermutePalindrome(string s) {
unordered_map<char, int> cnts;
for (char c : s) cnts[c]++;
bool foundSingle = false;
for (auto &p : cnts) {
if (p.second % 2) {
if (foundSingle) return false;
foundSingle = true;
}
}
return true;
}
};