Determining if a string is a palindrome of a permutation

Question

I wrote code to determine if a string is a palindrome of a permutation. This exercise was taken from Cracking the Coding Interview. I'm looking for any tips on improving it.

#include <iostream>
#include <string>

/*
*   Determine if a string is a palindrome of a permutation.
*   For simplicity, assume each string contains ONLY alphabetical characters.
*/

//strip string of non-alphabetical characters
std::string strip_junk(std::string s){
    std::string output("");
    for(char& c : s)
        if(isalpha(c)){
            c = tolower(c);
            output += c;
        }
    return output;
}

//determine how many times each character appears in the string
int *get_char_counts(std::string input){
    static const int ascii_sub = 97;
    static int counters[26]{0};
    for(char c : input){
        counters[c - ascii_sub]++; //if c='a', c-ascii_sub = 0. if c='z', c-ascii_sub = 25
    }
    return counters;
}

//check if more than one character appears an odd number of times
bool check_chars(std::string input){
    int *char_counter = get_char_counts(input);
    bool flag = false;
    for(int i = 0; i < 26; ++i){
        if(*(char_counter + i) % 2 != 0){ //if number is odd, check if it appeared twice
            if(flag)
                return false; //it appeared twice, return false
            flag = true;
        }
    }
    return true;
}

//check if string is a palindrome of a permutation
bool palindromePermutation(std::string input){
    input = strip_junk(input);
    return check_chars(input);
}

int main(void){
    std::string input;
    std::getline(std::cin, input);
    std::cout << (palindromePermutation(input) ? "True" : "False") << std::endl;
}

Answer 1

I'd change a number of things in this code.

std::string output("");

No need for the empty initializer--it'll be initialized to an empty string by default (i.e., std::string output; is fine).

for(char& c : s)
    if(isalpha(c)){
        c = tolower(c);
        output += c;
    }

I don't see where you gain anything by modifying the input string here, instead of just writing the modified character to the output:

for (char c : s)
    if (isalpha(c))
        output += tolower(c);

Unfortunately, things aren't quite that simple. In most implementations, a plain char is signed, and passing a negative number to isalpha or tolower gives undefined behavior. Anytime you call either, you really need to convert to unsigned char first:

for (unsigned char c : s) 
    if (isalpha(c))
       output += tolower(c);

Now when somebody tests with (for example) an accented character, it won't crash and burn.

static const int ascii_sub = 97;

This strikes me as wrong in at least a couple of different ways. First, the name strikes me as poor (ASCII, as such, is mostly obsolete, and even before that, it was unnecessarily narrow). I guess you mean the sub to refer to subtraction (somehow or other) but it's not immediately apparent how the two combine meaningfully.

Worse, it appears that your real intent is to just get the value of a. If you want that, it's almost always better to just use 'a'.

static int counters[26]{0};

Here I'd rather use something like static size_t counters['z'-'a']; Since it's static, it'll be initialized to zeros automatically. Using 'z' - 'a' makes it apparent what that 26 is intended to signify--and as a bonus, even makes it work with systems that use EBCDIC, where the distance from a to z is more than 26.

And, of course, the standard type for counting things where you can't ever have negative values is size_t (though a signed int like you've used will typically be perfectly fine).

Rather than using a static array, I'd probably use a std::vector (not static, and return it by value rather than returning a pointer to it).

Looking at check_chars, I think I'd do things a bit differently. I'd probably use std::find_if to do the searching, something like this:

auto first = find_if(counts.begin(), counts.end(), [](size_t s) { return s % 2 != 0); });

auto second = find_if(first, counts.end(), [](size_t s) { return s % 2 != 0; });

return second != counts.end();

The first tries to find an odd value. The second tries to find a second odd value between the first, and the end. If the first failed, it'll return counts.end(). The second will try to search between the end and the end, and obviously conclude no such thing exists (very quickly), so it'll return counts.end() as well.

Finally this:

std::cout << (palindromePermutation(input) ? "True" : "False") << std::endl;

...can be simplified a bit as well:

std::cout << std::boolalpha << palindromePermutation(input) << "\n";

std::boolalpha is not only a bit shorter, but also uses the names defined in the locale, so when using (for example) a German locale, it could print out falsch and wahr (and with a Chinese locale, if Google Translate is to be trusted, 假 and 真) for "false" and "true", respectively.