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) {
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;
}
};