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

bool canPermutePalindrome(string s) { // time: O(n); space: O(1)
    if (s.empty()) return false;
    vector<int> record(128, 0);
    for (char c : s) ++record[c];
    int odd = 0;
    for (int num : record) {
        if (num & 1) ++odd;
        if (odd > 1) return false;
    }
    return true;
}

bool canPermutePalindrome(string s) { // time: O(n); space: O(1)
    unordered_set<char> hashset;
    for (char c : s) {
        if (!hashset.count(c)) hashset.insert(c);
        else hashset.erase(c);
    }
    return hashset.size() <= 1;
}