Palindrome Permutation

1.4 Palindrome Permutation: Given a string, write a function to check if it is a permutation of a palindrome. A palindrome is a word or phrase that is the same forwards and backwards. A permutation is a rearrangement of letters. The palindrome does not need to be limited to just dictionary words.

EXAMPLE

Input: Tact Coa
Output: True (permutations:"taco cat'; "atco cta'; etc.)

• My first method involve using a hash table. While this algorithm will preform in O(N) time, we use a long of additional extra space.

• I first store the elements into a hash table, along with their frequencies, making sure to ignore spaces, and invalid characters.

• Next, I iterate through this hash table to check for valid frequencies. Even lengthed strings must have a frequencies of even elements, and odd length strings must have 1 single frequency char with the remainder of the characters having a even number of frequencies.

bool isPalindromic(string str) {
    if (str.length() < 2) return true;

    str.erase(remove_if(str.begin(), str.end(), isspace), str.end());
    transform(str.begin(), str.end(), str.begin(), ::tolower);
    unordered_map <char, int> char_frequency;

    for (auto i : str) {
        if (!isalpha(i)) continue;
        auto &found = char_frequency.find(i);
        if (found == char_frequency.end()) {
            // not found
            char_frequency.insert({ i, 1 });
        }
        else {
            // found
            found->second++;
        }
    }

    // count duplicates
    if (str.length() % 2 == 0) {
        // even
        for (auto i : char_frequency) {
            if (i.second != 2) {
                return false;
            }
        }
        return true;
    }
    else {
        // odd
        bool one_odd_flag = false;
        for (auto i : char_frequency) {
            if (i.second == 1 && !one_odd_flag) {
                one_odd_flag = true;
            }

            else if (i.second != 2 && one_odd_flag) {
                return false;
            }
        }
        return one_odd_flag;
    }
}

int main() {
    cout << boolalpha << isPalindromic("Tact Coa") << endl;
    cout << boolalpha << isPalindromic("asijdia") << endl;
    cout << boolalpha << isPalindromic("aassdd") << endl;
    cout << boolalpha << isPalindromic("asdasde") << endl;
    cout << boolalpha << isPalindromic("sdd") << endl;
    pause();
}

• The second approach is more attractive in my opinion, although it is a little less elegent. The approach is to first sort a valid string, and then compare the elements in place to confirm whether the next element is a duplicate. I've applied the same idea for when an element is odd, we allow for one free be.

• O(nlogn) time, O(1) space

bool isPalindromic(string str) {
    if (str.length() < 2) return true;

    str.erase(remove_if(str.begin(), str.end(), isspace), str.end());
    transform(str.begin(), str.end(), str.begin(), ::tolower);
    unordered_map <char, int> char_frequency;

    for (auto i : str) {
        if (!isalpha(i)) continue;
        auto &found = char_frequency.find(i);
        if (found == char_frequency.end()) {
            // not found
            char_frequency.insert({ i, 1 });
        }
        else {
            // found
            found->second++;
        }
    }

    // count duplicates
    if (str.length() % 2 == 0) {
        // even
        for (auto i : char_frequency) {
            if (i.second % 2 != 0) {
                return false;
            }
        }
        return true;
    }
    else {
        // odd
        bool one_odd_flag = false;
        for (auto i : char_frequency) {
            if (i.second % 2 != 0 && !one_odd_flag) {
                one_odd_flag = true;
            }

            else if (i.second % 2 != 0 && one_odd_flag) {
                return false;
            }
        }
        return one_odd_flag;
    }
}