Check string is permutation of palindrome

Question

I assume there can be space in between and I have ignored that. Also, there will be only lower case characters in the string.

My logic: There can be only one occurrence of odd number of character in palindrome string.

#include <iostream>
#include <algorithm>
#include <unordered_map>

using std::cout;
using std::endl;


int main(int argc, const char * argv[]) {


    char arr[] = "tact coa";

    std::unordered_map<char, int> m;

    size_t len = strlen(arr);

    for (int i = 0; i<len; i++) {

        if(arr[i] == ' ') continue; //ignoring space

        if(m.find(arr[i]) == m.end())
        {
             m[arr[i]] = 1;

        }
        else{
            m[arr[i]]++;
        }
    }

    int count = 0;

    for (int i = 0; i<len; i++) {

        if((m[arr[i]] % 2) == 1)count++;

    }
    if(count > 1) {cout<<"Not Palindrom"<<endl;}
    else {cout<<"Palindrom"<<endl;}

    return 0;
}

Answer 1

I would separate the algorithm from the main so that you can reuse your algorithm later.

The idea of using a hash-table based unordered_map is going into the right direction. However...

if(m.find(arr[i]) == m.end())
{
     m[arr[i]] = 1;
}

you don't need that initialization; you can think that each integer key is zero by default.

What comes to this:

for (int i = 0; i<len; i++) {
    if((m[arr[i]] % 2) == 1)count++;
}

In the loop, you can check whether the counter gets the value of 2, and exit as soon as you detect this, which adds to the efficiency of the routine.

All in all, I had this in mind:

bool is_palindrome_permutation(char* p)
{
    std::unordered_map<char, size_t> m;

    while (*p)
    {
        if (std::isalpha(*p))
        {
            m[*p]++;
        }

        p++;
    }

    size_t count = 0;

    for (auto& p : m)
    {
        if (p.second % 2 == 1)
        {
            if (++count == 2)
            {
                return false;
            }
        }
    }

    return true;
}

Hope that helps.

Edit 1

As additional fun, you can consider having a template, which allows you to abstract away the actual sequence implementation:

template<typename ForwardIter>
bool is_palindrome_permutation(ForwardIter begin, ForwardIter end)
{
    using value_type = typename std::iterator_traits<ForwardIter>::value_type;
    std::unordered_map<value_type, size_t> m;

    while (begin != end && *begin) // *begin: a dirty hack for correctness
    {                              // on zero-terminated C strings.
        m[*begin]++;
        ++begin;
    }

    size_t count = 0;

    for (auto& pair : m)
    {
        if (pair.second % 2 == 1)
        {
            if (++count == 2)
            {
                return false;
            }
        }
    }

    return true;
}

template<typename Sequence>
bool is_palindrome_permutation(const Sequence& seq)
{
    return is_palindrome_permutation(std::begin(seq), std::end(seq));
}


int main() {
    char str[] = "tacoota";
    cout << "Palindrome permutation: "
         << std::boolalpha
         << is_palindrome_permutation(str,
                                      str + sizeof(str) / sizeof(str[0]))
         << endl;

    std::string str2{"tacoota"};
    cout << "Palindrome permutation: "
         << is_palindrome_permutation(str2)
         << endl;

    std::vector<char> vec;
    std::copy(str2.begin(), str2.end(), std::back_inserter(vec));
    cout << "Palindrome permutation: "
         << is_palindrome_permutation(vec)
         << endl;
    return 0;
}