Checking if characters in a string can be rearranged to make a palindrome

Question

Can I please have some advice on optimizing, cleaning up my code, and places where I could save space/time?

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool pal_perm(char*);
int main()
{
    printf("The output is %sa palindrome.\n", pal_perm("abbas")? "": "not "); //Output: The output is a palindrome.
    printf("The output is %sa palindrome.\n", pal_perm("deeds")? "": "not "); //Output: The output is a palindrome.
    printf("The output is %sa palindrome.\n", pal_perm("dead")? "": "not "); //Output: The output is not a palindrome.
    return 0;
}

bool pal_perm(char* str)
{
    char alpha[256];
    int oddCount =0;
    int size = strlen(str);
    memset(alpha, 0, sizeof(alpha)); 

    //see how many occurances of each letter
    for(char ch = 'a'; ch <= 'z'; ch++)
    {
        for(int i=0; i < size; i++)
        {
            if(str[i] == ch)
                alpha[str[i]]++;
        }
    }

    //count the number of times a letter only appears once
    for(int j=0; j<256; j++)
    {
        if(alpha[j] == 1 || (alpha[j]%2==1))
            oddCount++;

    }
    //if there is more than one letter that only occurs, then it 
    //cannot be a palindrome.
    if(oddCount <= 1)
        return true;
    else
        return false;
}

Answer 1

Strange output

What is a user to think when seeing such output of a program?

The output is a palindrome.
The output is not a palindrome.

I wouldn't know what this program is trying to tell me.

Consider this alternative:

void print_result(char * s)
{
    printf("The characters of \"%s\" %s be rearranged into a palindrome.\n", s, pal_perm(s) ? "can" : "cannot");
}

int main()
{
    print_result("abbas");
    print_result("deeds");
    print_result("dead");
}

Output:

The characters of "abbas" can be rearranged into a palindrome.
The characters of "deeds" can be rearranged into a palindrome.
The characters of "dead" cannot be rearranged into a palindrome.

Though actually I would prefer something much simpler than that:

printf("\"%s\" -> %s\n", s, pal_perm(s) ? "true" : "false");

Producing output:

"abbas" -> true
"deeds" -> true
"dead" -> false

Usability

It would be more interesting if the program took the strings from the command line, instead of using hardcoded values, for example:

int main(int argc, char ** argv) {   
    for (int i = 1; i < argc; i++) {
        print_result(argv[i]);
    }
}

For the record, @Law29 suggested another alternative in a comment:

You can also read from standard input. This lets you either type in words as they come to mind, or use a whole file (there are files of dictionary words, for example). Example:

#define MAX_WORD_SIZE 50
int main(int argc, char ** argv) {   
    char buf[MAX_WORD_SIZE]
    while (fgets (buf, MAX_WORD_SIZE, stdin)) {
        print_result(buf);
    }
}

Testing

Getting the implementation right can be tricky. You revised your post 3-4 times to fix bugs pointed out in comments. It's good to automate your tests so that they can be repeated easily, for example by adding methods like these:

void check(char * s, bool expected)
{
    if (pal_perm(s) != expected) {
        printf("expected \"%s\" -> %s but got %s\n", s, expected ? "true" : "false", expected ? "false" : "true");
        exit(1);
    }
}

void run_tests()
{
    check("a", true);
    check("aa", true);
    check("aba", true);
    check("abba", true);
    check("aabb", true);
    check("aabbs", true);
    check("deeds", true);

    check("ab", false);
    check("abc", false);
    check("dead", false);
}

Use boolean expressions directly

Instead of this:

if(oddCount <= 1)
    return true;
else
    return false;

You can simply return the boolean expression itself:

return oddCount <= 1;

Excessive looping

As @DarthGizka explained, instead of this:

for(char ch = 'a'; ch <= 'z'; ch++)
{
    for(int i=0; i < size; i++)
    {
        if(str[i] == ch)
            alpha[str[i]]++;
    }
}

This is identical, but without unnecessary looping:

for(int i=0; i < size; i++)
{
    alpha[str[i]]++;
}

Unnecessary conditions

The first condition is unnecessary:

    if(alpha[j] == 1 || (alpha[j]%2==1))

This is exactly the same:

    if(alpha[j]%2==1)

Too compact writing style

Instead of this:

    if(alpha[j]%2==1)

I suggest to put spaces around operators, and before ( in if statements:

    if (alpha[j] % 2 == 1)

Stop iterating when you already know the result

Once you find two characters with odd number of occurrences, you can stop iterating and return false. As such, you don't even need an int oddCount, but a bool seenOdd. So instead of this:

int oddCount = 0;

//count the number of times a letter only appears once
for (int j = 0; j < 256; j++)
{
    if (alpha[j] % 2 == 1) oddCount++;
}
//if there is more than one letter that only occurs, then it 
//cannot be a palindrome.
return oddCount <= 1;

You could write:

bool seenOdd = false;

// scan for odd number of occurrences, stop after seeing two
for (int j = 0; j < 256; j++)
{
    if (alpha[j] % 2 == 1) {
        if (seenOdd) return false;
        seenOdd = true;
    }
}

// less then 2 letters with odd number of occurrences, must be true
return true;

Answer 2

Your code scans the string much more often than necessary. Also, iterating over a hard-coded range of characters (from 'a' to 'z') is not only superfluous, it will cause your code to fail when characters outside that range appear.

A string can be rearranged to make a palindrome iff it contains no more than one character with an odd occurrence count. Single-character strings can be excluded with a trivial test if so desired.

Hence the idea is to iterate over the characters in the string to count their occurrences, and to see how many of them have an odd number of occurrences.

The only thing that matters about the occurrence count for a character is whether it is odd or not. This means that things are still okay if you count modulo some convenient modulus, like 256 (leading to byte-sized counters) or 2 (leading to an array of booleans or a bit array).

However, fixed-size arrays can become really awkward (i.e. big) unless the range of allowable characters is tightly bounded, for example restricted to 7-bit ASCII characters. The reason is that Unicode has untold millions of character code points, and creating a fixed-size counter array to accommodate them all takes lots of memory even if you use only a single bit per counter.

Hence, either restrict the range of allowable characters, or use a dynamic mapping mechanism so that you only have to deal with the characters that actually occur in the string.

Thus the recommended plan for an optimised version of your code is this:

• make a single pass over the input string to count character occurrences
• make a single pass over the occurrence counters to see if there's more than one odd count

Answer 3

In this alternative

    (alpha[j] == 1 || (alpha[j]%2==1))

if the first part is true, then the second one is true, too, so there's no need to keep them both — just use

    if(alpha[j] % 2)
        oddCount++;

or, a bit faster,

    oddCount += alpha[j] % 2;

This could be made even faster thanks to observation you don't actually need a count of each character, but only the information if the count is even or odd. Then you can replace the counter array char alpha[] with a flag array, and just flip the flag when necessary instead of incrementing. Finally you just count the odd characters:

    int  charodd[256];
    memset(charodd, 0, sizeof charodd);

    int size = strlen(str);
    for(int i=0; i<size; i++)
    {
        unsigned int j = (unsigned char)str[i];

        charodd[j] = ! charodd[j];
    }

    int oddCount = 0;
    for(int j=0; j<256; j++)
    {
        oddCount += charodd[j];
    }

Answer 4

My am giving 2 solutions. IDEA => There must be 1 or no odd element in the String. Therefore we will do a check ch %2 == 1 then it will be a palindrome or else not.

Solution1: Java(using HashSet)

//Check if a given string is a rotation of a palindrome
public class test7 {

    public static void main(String[] args) {
        String s = "Protijayi";

        Set<Character> set = new HashSet<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (set.contains(ch)) {
                set.remove(ch);

            } // if
            else {
                set.add(ch);
            }
        } // for

        if (set.size() <= 1) {
            System.out.println("can be converted into a palindrome");
        } else {
            System.out.println("cannot be a palindrome");
        }

    }
}

In Python : we will do a list comprehension using Counter and we will count how many odd numbers are there.

from collections import Counter


def fix(a):
    return len([  v for v in Counter(a).values() if v % 2 == 1]) <= 1


a = "mmdaa"
print(fix(a))

Answer 5

Accept string literals

I get this warning when I compile:

115308.c:9:56: warning: passing argument 1 of ‘pal_perm’ discards ‘const’ qualifier from pointer target type [-Wdiscarded-qualifiers]
     printf("The output is %sa palindrome.\n", pal_perm("abbas")? "": "not "); //Output: The output is a palindrome.
                                                        ^~~~~~~
115308.c:6:15: note: expected ‘char *’ but argument is of type ‘const char *’
 bool pal_perm(char*);
               ^~~~~

That's easily fixed by declaring the function to accept const char*:

bool pal_perm(const char*);

Don't index arrays using char

char may be a signed type, so it's a poor choice here:

        if (str[i] == ch)
            alpha[str[i]]++;

We need to convert str[i] to unsigned char to be safe.

Don't assume a particular range for unsigned char

The standard library gives us UCHAR_MAX, so we should use that when creating our array:

char alpha[UCHAR_MAX + 1];

And when populating it:

for (int j = 0;  j <= UCHAR_MAX;  ++j)

Don't overflow signed types

char is a poor choice for these counters - if there are more than CHAR_MAX of any given character in the input, then the code is undefined. If we use an unsigned type instead, then we can increment it safely. (Though, as other answers suggest, we don't need to count, as we're only interested in the parity of each element.)

Use standard character classification functions

Include <ctype.h> to get isalpha(), which is a more accurate (and locale-adaptive) replacement for your a..z test.

Make a single pass over the string

We don't need to measure the string length with strlen() (but if we did, we should use size_t rather than int to store the result). Instead, we can simply traverse until we see a NUL character. And we can use our copy of the pointer passed in to the function, since we won't need it again:

bool alpha[UCHAR_MAX + 1] = {0};

while (*str) {
    unsigned char c = (unsigned char)*str;
    if (isalpha(c)) {
        alpha[c] = !alpha[c];
    }
    ++str;
}

Accept inputs from command-line

Instead of hard-coding the strings to test, allow them to be provided by the user. Here's an example:

int main(int argc, char **argv)
{
    const char *const message[] = {
        "'%s' cannot be rearranged to a palindrome\n" ,
        "'%s' has at least one palindromic permutation\n"
    };

    for (int i = 1;  i < argc;  ++i) {
        const char *const s = argv[i];
        printf(message[pal_perm(s)], s);
    }
}

I've changed the printing so that it's not "Lego constructed" by bolting together phrases. The latter approach can be hard to translate, compared with the former.

---

Modified code

#include <ctype.h>
#include <limits.h>
#include <stdio.h>
#include <stdbool.h>

bool pal_perm(const char* str)
{
    bool unpaired[UCHAR_MAX + 1] = {0};

    while (*str) {
        unsigned char c = (unsigned char)*str;
        if (isalpha(c)) {
            unpaired[c] = !unpaired[c];
        }
        ++str;
    }

    // count the number of letters that are not paired
    int oddCount = 0;
    for (int i = 0; i < UCHAR_MAX;  ++i)
    {
        if ((oddCount += unpaired[i]) > 1)
            return false;
    }

    // if we got here, there's at most 1 unmatched letter
    return true;
}

int main(int argc, char **argv)
{
    const char *const message[] = {
        "'%s' cannot be rearranged to a palindrome\n" ,
        "'%s' has at least one palindromic permutation\n"
    };

    for (int i = 1;  i < argc;  ++i) {
        const char *const s = argv[i];
        printf(message[pal_perm(s)], s);
    }
}