Return to Revisions

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

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.

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 to store our values (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[c] = !hist[c];
}

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

That reduces the code to a much simpler version:

#include <bitset>
#include <climits>
#include <string>

bool isPalinStr(const std::string& a)
{
    std::bitset<UCHAR_MAX+1> hist;
    for (unsigned char c: a) {
        hist[c] = !hist[c];
    }

    return hist.count() <= 1;
}

#include <cassert>
#include <iostream>
int main()
{
    assert(isPalinStr("aabbccd"));
    assert(!isPalinStr("aabbcd"));
}