# Palindrome Permutation string

I’m starting to learn C++ by doing a lot of exercises, and I need your help so I can improve, Here is how it goes, I will try to solve an exercise and post both the exercise and my solution to it, And I want you to point me to where / what improvements I can do to make my code better, this would help me both uncover missing parts that I didn’t know about, and better ways of coding, alternative coding style or features introduced in C++11 C/++14/C++17/C++20 are welcomed to be mentioned, with some code snippet if possible, as I'm trying to write some modern C++ as possible while learning, it help in adopting as a habit.

Here it is

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.

Here is my solution

#include <iostream>
#include <string>
#include <cassert>
#include <vector>
#include <unordered_map>

bool isPalinStr(const std::string& a) {

std::unordered_map<char, int> x;

if (a.length() % 2 == 0) {
for (int i = 0; i != a.length(); ++i) {
x[a[i]] += 1;
}
for (auto& ch : x) {
if (ch.second % 2 != 0)
return false;
else {
return true;
}
}
}
else {
for (int i = 0; i != a.length(); ++i) {
x[a[i]] += 1;
}
unsigned  even = 0;
unsigned  odd = 0;
for (auto& ch : x) {
if (ch.second % 2 == 0)
even++;
else {
odd++;
}

}
if (even % 2 == 0 && odd == 1) {
return true;
}
else {
return false;
}

}
}

int main() {

assert(true == isPalinStr("aabbccd"));
assert(false == isPalinStr("aabbcd"));

return 0;

}


Hey reader you might want to check other parts :

• Isn't a permutation of a palindrome of a word simply a permutation of the word? Aug 23, 2022 at 10:46
• Please don't use the x86 tag, when you just want performance. There is nothing in these types of exercises that is worth making architecture-specific optimizations for. Also, the entire Code Review site is about making code improvements, so you don't have to put "code improvements" in the title of every question. Aug 23, 2022 at 15:24
• If you're targeting C++20, and want the code reviewed with the latest language features in mind, then just pick the c++20 tag. Aug 23, 2022 at 15:28

#include <vector> is unnecessary for this program.

There are clearly insufficient tests, because there's a bug here:

    for (auto& ch : x) {
if (ch.second % 2 != 0)
return false;
else {
return true;
}
}


This means that we only ever inspect the first value in the histogram, and ignore the later ones.

And we have undefined behaviour when given the empty string, because we don't reach any return statement before the end of the function. A decent compiler should spot that for you if you ask for its help; this suggests you need to enable more warnings when you compile.

We have a strange test here:

    if (even % 2 == 0 && odd == 1) {
return true;
}
else {
return false;
}


It doesn't matter how many matched pairs of characters we have, so the count of how many even histogram counts we found is irrelevant. This will fail "aba" for instance, as we only have a single even count. We really just need to test that we have 0 (for even-length strings) or 1 (for odd-length) odd-size counts.

Note also that the general pattern if (condition) return true; else return false; can always be replaced by return condition;.

A good practice to follow when bugs such as these are identified is to add tests which reproduce the bug; when they are made to pass, the tests remain as part of the program's test suite to guard against reintroducing similar bugs. That way, we gradually increase the number of valuable tests as we progress.

This code is repeated in both branches of the initial if:

    for (int i = 0; i != a.length(); ++i) {
x[a[i]] += 1;
}


Instead of writing it twice, we should bring it out before the if so it's only present once. The index variable i should be a std::size_t so that it can be compared against any length() (another compiler warning to enable there!).

We can simplify it (and improve the name of the histogram variable):

for (auto c: a) {
++hist[c];
}


Our histogram maps char to int, which could potentially overflow (undefined behaviour again). We could use an unsigned type (which has well-defined overflow behaviour), but consider that we're only interested in whether the value is even or odd - so we could use a map from char to bool to store our values modulo-2.

Also, an unordered map is a pretty slow form of histogram. For reasonable systems, with CHAR_BIT in the 8-16 range, we could use a simple array or a bitset (though we'll need to convert the string's characters to unsigned char to avoid indexing out of range):

std::bitset<UCHAR_MAX+1> hist;
for (unsigned char c: a) {
hist.flip(c);
}


When we have done this, we can simply use bitset::count() (or std::count() on an array) to tell us how many characters appear an odd number of times.

That reduces the code to a much simpler function:

#include <bitset>
#include <climits>
#include <string_view>

bool isPalinStr(const std::string_view s)
{
std::bitset<UCHAR_MAX+1> hist;
for (unsigned char c: s) {
hist.flip(c);
}

return hist.count() <= 1;
}

#include <cassert>
#include <iostream>
int main()
{
assert(isPalinStr(""));
assert(isPalinStr("a"));
assert(isPalinStr("aa"));
assert(isPalinStr("aabb"));
assert(isPalinStr("abbcc"));
assert(isPalinStr("aabccdd"));
assert(isPalinStr("aabbccd"));

assert(!isPalinStr("ab"));
assert(!isPalinStr("abc"));
assert(!isPalinStr("abbb"));
assert(!isPalinStr("aabbcd"));
}

• Good use of unsigned char vs. char. isPalinStr() here is poetic. Aug 22, 2022 at 18:30
• Of course an array of some unsigned type (byte up to register size) might be more efficient (code and time, not stack). Only measuring will show. Aug 22, 2022 at 20:02
• @Deduplicator, yes that may well be true, and I did start with a std::array<bool>. But the convenience of bitset::count() swung me! Aug 22, 2022 at 20:11
• Yes, std::ranges::count_if(hist, [](auto x){return x % 2; }); would be a bit more verbose. Aug 24, 2022 at 0:21
• I was imagining counting mod 2, which is a bit shorter (hist[c] ^= 1 in the loop, then std::ranges::accumulate() to count the ones); even then, the bitset is more convenient. Aug 26, 2022 at 11:30

You don't need to keep track of even at all, and you don't need to keep track of odd as an int. You just need to keep track of whether you've seen an odd number, and if you have, return false the next time you see another one.

You can replace x[a[i]] += 1; with x[a[i]] = !x[a[i]];. Then replace the code

for (auto& ch : x) {
if (ch.second % 2 == 0)
even++;
else {
odd++;
}

}


with

previous_odd = false
for (auto& ch : x) {
if ch.second {
if previous_odd {
return false;
}
previous_odd = true;
}
}
return true

• Thanks for adding this. I meant to point out that we could return early, but forgot that in the rest of my review. Aug 23, 2022 at 6:52

### Write out names

bool isPalinStr(const std::string& a) {


What does that Alaskan reality TV star (or the actor if searching from the UK) have to do with your code?

There is no need to put types in C++ function names, as C++ has function overloading.

bool canBePalindrome(const std::string& a) {


Requires no thinking to understand what is being checked. Even if readers aren't familiar with what a palindrome is, they can look it up. If someone tries to look up palin, they will have to wade through many irrelevant results. And that's if palindrome ever appears.

In general, it is best to optimize code to be easy to read. Because you read code far more often than you write it.

### Don't mix statement and block forms

            if (ch.second % 2 == 0)
even++;
else {
odd++;
}


Please never do this. If you are going to use the statement form for single statement blocks, use it every time (except in an if/else with the other using the block form). If you are going to use the block form (and there is a good argument to always use the block form) for single statement blocks, then use it everywhere.

Mixing the block and statement forms in the same if/else construct is questionable even if one requires a block. Mixing them like this is the worst of all worlds. You lose the minimal gains of shorter code and make the code more complex than simply using the block form everywhere.

Note that a simpler version of this would be

std::size_t remainderCounts[2] = {0, 0};
for (auto ch : x) {
remainderCounts[ch.second % 2]++;
}


As noted elsewhere, you do not need to count either evens or odds. You only need to know if there were zero, one, or more than one odd values. If zero or one, then a palindrome. If more than one, not. But if you did need to check these things, then you could reduce your lines of code by using a better data structure.

• Michael Palin is English, not Alaskan. Unless you were thinking of someone else? Aug 24, 2022 at 5:03
• isPalindrome() is a misleading name; isAnagramOfPalindrome() is more accurate. There could be problems with using either in the global namespace with any code that includes the (deprecated) <ctype.h>. Aug 24, 2022 at 5:05
• @TobySpeight Conciseness is a virtue. isScrambledPalindrome() is more like it. Aug 26, 2022 at 8:53
• Yes @Deduplicator, that's much better. As they say, "the two hard problems in computing..." Aug 26, 2022 at 11:31

In C++ performance is improved by using iterators rather than indexing through arrays. Iterators point directly to the data rather than needing to be indexed.

I asked a very similar question several years ago.

bool IsPalindrome(const std::string& s) {
return std::equal(s.begin(), s.begin() + s.size() / 2, s.rbegin());
}


The unordered_map you are using adds too much overhead and shouldn't be necessary.

You need to become comfortable with the concepts of pointers even if you don't use them directly (iterators may use pointers, they definitely use concepts of pointers).

Pointers are a major concept in C and were carried over to C++.

• "caacbb" this won't pass your code ! but it still it is Palindrome Permutation string Aug 22, 2022 at 16:26
• I think you misunderstood the problem statement @pacmaninbw - the requirement is that the letters can be arranged into a palindrome, i.e. at most one odd value in the histogram. Aug 22, 2022 at 16:52
• @TobySpeight It is quite possible I misunderstood the problem statement. I still feel that the OP needs to learn about iterators, and other standard library features. Aug 22, 2022 at 17:53
• Oh yes, you're absolutely correct there. Aug 22, 2022 at 19:55
• I have never seen any significant performance improvements caused by using iterators rather than indexing for arrays. I see it as a matter of preference. Also related answer, stackoverflow.com/a/2524322. Aug 25, 2022 at 21:07

I would like to propose some general code style improvements without discussing the idea of the original solution.

bool isPalindrome(const std::string& word)  // prefer using meaningful names
{                                           // consider replacing redundant line break with an opening curly brace
std::unordered_map<char, int> freqs;    // freqs is for frequencies. We may use a better suitable short name, if there is one
for (char ch : word)    // prefer range-for loop for iterating over the whole container for brevity
++freqs[ch];    // increment to make the code look idiomatic
// prefer omitting curly braces for statement bodies that fit in one line
if (word.length() % 2 == 0) {
for (const auto& p : freqs) // would prefer p for pair, since we use pair-specific syntax in the loop body
return p.second % 2 == 0;
// leave one empty line after return, break or continue to emphasize an early redirection of an execution flow
return true;    // necessary, if the word is empty
}   // else is redundant here because we return from the function early

unsigned even = 0;
unsigned odd = 0;
for (const auto& p : freqs) {    // it is better to make a variable const, if it is known to be immutable
if (p.second % 2 == 0)
++even;
else
++odd;
}

return even % 2 == 0 && odd == 1;
}


Regarding the code structure, one should also avoid duplicate code.

I suggest you to develop and follow a reasonable code style to make your code look comprehensible.