Palindrome Permutation

Given a string, determine if a permutation of the string could form a palindrome.

Example Given s = "code", return False. Given s = "aab", return True. Given s = "carerac", return True.

Solution: Count number of odd occurances Using Array

We can count the number of odd occurances in one pass. If there's more than 1 odds, then we return false.

    bool canPermutePalindrome(string &s) {
        // write your code here
        int arr[256] = {0};
        for (auto ch: s) arr[ch]++;

        int oddCount = 0;
        for (int i=0; i<256; i++) {
            if (arr[i] % 2) oddCount++;
            if (oddCount > 1) return false;
        }
        return true;
    }

Solution: Count number of odd occurances Using Set

The insert function will return a pair, with its member pair::first set to an iterator pointing to the element, and pair::second element set to true if a new element was inserted, or false it an equivalent element already exists.

    bool canPermutePalindrome(string &s) {
        // write your code here
        set<char> set;
        for (auto ch: s) {
            if (!set.insert(ch).second) {
                set.erase(ch);
            }
        }
        return set.size() <= 1;
    }