Anagram palindrome checking

Question

I need to figure out if any anagram of the string can be a palindrome or not.

Ideas:

It relies on two observations:

1. Frequency of every character in the string is even, if length of the string is even.

2. Frequency of every character in the string is even except for one character, where frequency must be odd if the string length is odd.

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

bool sortAsc(char c, char d) { return c<d; }
int main() {
    string s;
    cin>>s;
    sort(s.begin(), s.end(), sortAsc);
    int flag = 0;
    string::size_type i=0;

    //Even - number of characters whose frequencies are even
    //Odd - number of characters whose frequencies are even
    int even=0, odd=0;

    //The number of times the loop runs is size-1
    //because of the reason below
    while(i<s.size()-1) {
        int temp=0;

        //checking if the next char is same as current
        //if i will be size-1 then s[i+1] will be out of bound
        while(s[i]==s[i+1]) {
            ++temp;
            ++i;
        }

        //if the last element has only one occurrence
        //then it should be counted as a character with odd occurrence 
        if(i==s.size()-2) {
            //don't increment temp if
            //i is the second last element, just skip everything outside
            if(s[i]!=s[i+1]) { ++odd; ++i; continue;}
        }


        ++temp;
        if(temp%2==0) { ++even; } else { ++odd; }
        ++i;
    }

    if(s.size()%2==0 && odd == 0 || s.size()%2 != 0 && odd == 1) 
        flag=1;
    else
        flag=0;

    //I could have directly echoed them to console
    //but its just the way here
    if(flag==0)
        cout<<"NO";
    else
        cout<<"YES";

    return 0;
}

As you can see the following block is only used once but condition is checked in every iteration.

if(i==s.size()-2) {

    if(s[i]!=s[i+1]) { ++odd; ++i; continue;}

}

It just just there because s[i+1] if i==size will return error.

Question:

1. Is there any way I can loop until the last index and can still check if the last element has any occurrences?
2. Can it be done better without the initial sorting?

Answer 1

I think you might be overcomplicating the whole thing.

How do you define a palindrome? No matter which direction you're reading it, it's the same word. As you mentioned already, this means that all occurences of characters have to be even, except for one, which might be odd. However, the string length doesn't matter for this (it's just a logical consequence):

All characters with even occurences don't matter and can be ignored. You only have to count the number of characters who've got an odd count.

• With no odd count: abccba - this is a palindrome.
• With one odd count: abcba - this is a palindrome as well.
• With two odd counts: abcdba - this isn't a palindrome.

So the task boils down to one simple task: Count the number of odd character counts.

---

Some code things I've noticed:

• Try to avoid using using namespace. It might bite you in the back once you've got ambigious code and accidently call (or pass) the wrong function and you're unable to find the reason for some bug.

• Try to be more consistent with your whitespace characters. In some places you've put them there, in other cases you've omitted them. Overall this makes your code quite a bit harder to read (at least for me).

• Don't use single-char variables (a, i, k, etc.) unless they're iterators. This isn't JavaScript. You usually don't have to optimize code size. Instead use talking variable names, even if it's just "index" or "offset".

• I'd also try to use a constant value rather than calling specific members over and over again, if you don't expect them to change. In your case this would be the check inside your loop: while(i<s.size()-1) { You don't know what's happening inside std::string::size(). While highly unlikely, this might actually iterate over your whole string every loop to determine the current length, making your code even more inefficient. Just ensure your compiler knows it's going to be constant:

    const std::string::size_type length = s.size();
    while(i < length - 1) {
        // ...
    }
  

---

In your solution you start by sorting the whole string (which is most likely O(n²)). After this you're iterating over all elements a second time to do the actual counting (O(n)).

To me this is quite suboptimal, especially if you're able to use some memory for this.

I'd try something like the following code, which will iterate over the input string and count the occurences of every character (O(n)). In a second loop I count the number of even and odd occurences (O(1)).

#include <iostream>

int main(int argc, char **argv) {
    // Let's just assume argv[1] holds the string

    // This will hold all character counts, initialized to 0
    unsigned char counts[256] = {0};

    // Iterate over the string...
    for (unsigned char *pos = reinterpret_cast<unsigned char *>(argv[1]); *pos; ++pos)
        ++counts[*pos]; // ...and count

    // Counts for even/odd:
    // - Even -> index 0
    // - Odd -> index 1
    unsigned int eo[2] = {0};

    // Now iterate over all characters
    for (unsigned int i = 0; i < 256; ++i)
        ++eo[counts[i] % 2];

    if (eo[1] > 1) { // More than one odd count - can't be an anagram
        std::cout << "No anagram can be a palindrome, since there are multiple unique characters." << std::endl;
        return 0;
    }

    // At most one odd count; this can be an anagram
    std::cout << "There might be an anagram that is a palindrome." << std::endl;
    return 0;
}

The big advantage here in my opinion is the fact that there's no branching outside any loop construct (except that one final check).

You could however, just skip the counting of even/odd counts and use a single bool to determine whether you've got a second occurence of an odd count (which would mean that you don't have any palindrome).