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;
}

• greybeard: (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;

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;
}

• Incomputable: 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.
• coderodde: @Olzhas So your point is that we can treat a class as the alphabet?
• Incomputable: 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
• coderodde: @Olzhas Would a template function be in order?
• Incomputable: 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.