Palindrome Permutation string

Question

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 :

• [ exercise 1 ] string permutation
• [ exercise 2 ] space encoder for URL

Answer 1

#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"));
}

Answer 2

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

Answer 3

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.

Answer 4

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.

The simplest answer was

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++.

Answer 5

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.