1
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ (The distribution of white-space starting from the declaration of count is questionable). for (int single = 0 ; 0 <= --len ; ) if((m[arr[len]] % 2) && !(single ^= 1) { cout << "Not "; break; } cout<<"Palindrom"<<endl; \$\endgroup\$ – greybeard Oct 10 '16 at 7:15
2
\$\begingroup\$

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;
}
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ I would like to add that algorithm would be complete if you would make it work on iterator ranges. You could create an overload for const char* str, which will call main algorithm with str, str + strlen(str). The code needs minimal changes to be generic. \$\endgroup\$ – Incomputable Oct 9 '16 at 18:32
  • \$\begingroup\$ @Olzhas So your point is that we can treat a class as the alphabet? \$\endgroup\$ – coderodde Oct 10 '16 at 12:40
  • \$\begingroup\$ Dealing with spaces actually adds needless noise. That restriction will make the code fallback to this: iterator should be forward iterator, and *it always should be char& or char. I was just thinking if the algorithm makes sense in problems without strings. About your question: no. The algorithm you've written will be the same, just the condition in while will change and parameters too. I believe you can make it work with input iterators too \$\endgroup\$ – Incomputable Oct 10 '16 at 18:07
  • \$\begingroup\$ @Olzhas Would a template function be in order? \$\endgroup\$ – coderodde Oct 10 '16 at 18:13
  • \$\begingroup\$ I'm not really sure if I understand the question. If you mean why would one write it, it's because sometimes your input is not a string or a vector, so copying it would lead to overhead of copying it into string. I'm not really sure what order you mentioned. \$\endgroup\$ – Incomputable Oct 10 '16 at 18:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.