It's quite simple actually. If string has an even number of chars, just verify that every char in the string is present an even number of times, if string is odd, you're allowed one (and only one) unique char odd number of times (for the middle of the palindrome), rest of the characters should be even.

You don't need to create a palindrome. You just need to know the word could create a palindrome. e.g. say you have one a and one b. You can't create a palindrome but if you have an odd number of a and an even number b you can create a palindrome. (with half the b's followed by the a's followed by half the b's)

You can have at most one odd numbered letter (in the middle) All the other letters must be even numbered (you can add to the start and finish)

String s = args[0];
BitSet count = new BitSet();
for(int i=0;i<s.length();i++)
    count.flip(s.charAt(i)-'a'); // is the count odd or even.
boolean canBePalindrome = count.cardinality() <= 1; // at most one odd.

This may well be the quickest solution:

public static boolean isAoP (String s) {
    char[] c = s.toCharArray();
    int b = 0;
    for (int i = 0; i < c.length; i++) b ^= 1 << (c[i] - 'a');
    return (b & (b - 1)) == 0;
}
int isAnagramOfPalindrome (String s) { return isAoP(s) ? 1 : 0; }  // silly spec

This solution relies on the following facts:

• A string is an anagram of a palindrome if and only if at most one character appears an odd number of times in it.

• The specification stated that the input can only contain the 26 lowercase letters a – z, which have consecutive codepoints in Unicode.

• A Java int is 32 bits long, and so can store one bit for each of the allowed letters.

• The expression b & (b - 1) evaluates to zero if and only if b has at most one bit set.

I think you just need to scan input once, from start to end, and count how many times each char in input is encountered. If at the end, each char is encountered exactly twice, except one char, which is encountered once, you have palindrom (albeit, it can be not an English word).

This requires O(1) memory, because to count you need array of 25 26 cells, one cell per English alphabet's letter.

UPDATE yes, I've missed even number of chars in input, in that case, all chars must be encountered twice, as solendil correctly noticed. Well, for empty input of even length 0, you don't need to count anything.

Step - 1 ) Scan the input

Step - 2 ) Determine the length of input.

Step - 3 ) if length is odd then count of all the characters must be multiple's of 2 , except for one

Step - 4) If length is even then count of all the characters must be multiple of 2.

So basically if the given string even though not a palindrome but has the properties of becoming a palindrome ( by shuffling the characters around) then it should be an anagram of a palindrome.

Thats the concept here

Count the number of times each character appears in the string. If the string's length is an odd number, it's a palindrome if each character appears an even number of times, except for one (the one in the middle of the original string). If the length is even, each character must appear an even number of times.

Devised a method which applies only when all the characters of the string are from lower case alphabets:

Loop through all the characters of the string and toggle the (offseted) bit position of the characters. If the resulting value of bit array is either zero or power of two, then it is anagram of palindrome

unsigned int check_bitarray(char *str, unsigned int size)
{
    unsigned int i, temp = 0;

    for (i = 0; i < size; i++) {
        temp ^= 1 << (str[i] - 97);
    }

    if (!temp | !(temp & (temp - 1)))
        return 1;

    return 0;
}

Change the offset 97 appropriately if the string has chars only from numerical or upper case alphabets.

Implementing the solution proposed by solendil in Java:

public static boolean isAnaPalindrome(String input)
{
    boolean isOdd = input.size();
    boolean allowFirstOdd = idOdd;
    Map<Char,Integer> freq = new MapList<Char,Integer> ();

    for (char c : input.c_str())
    {
        if (freq.containsKey(c))
        {
            freq.set(c, freq.get(c)+1);
            unique.add(c);
        }
        else freq.add(c, 1);
    }

    for (Char c : freq.keySet())
    {
        // odd occurrence
        if (freq.get(c) % 2 != 0)
        {
            if (allowFirstOdd)
                allowFirstOdd = false;
            else
                return false;
        }
    }

    return true;
}

My solution in Javascript:

// Declare vars
var strTest = 'rocketboys';

if (isAnagramOfPalindrome(strTest.toLowerCase()))
  console.log ('"' + strTest + '" is a Palindrome');
else
  console.log ('"' + strTest + '" is not a Palindrome');

// Declare function that provides the solution
function isAnagramOfPalindrome(S) {

  var len = S.length;

  var firstHalf = len % 2 == 0 ? S.substring(0, (len/2)) : S.substring(0, len/2);
  var middleChar = len % 2 == 0 ? null : S.charAt(len/2);
  var secondHalf = len % 2 == 0 ? S.substring(len/2, len) : S.substring(len/2 + 1, len);

  var middleIndex = len % 2 == 0 ? len/2 : len/2 - 1;
  var isPalindrome = true;

  for (var i = 0, j = secondHalf.length - 1; i < middleIndex; i++, j--) {
    if (firstHalf.charAt(i) != secondHalf.charAt(j))
      isPalindrome = false;
  }

  return isPalindrome;

}

First of all, the length of the input string must be even, otherwise it can not be a palindrom. Then it is enough to check for every input string's character if there is another occurence of the same character in the string. For example:

public int isAnagramOfPalindrom(String s) {
    int len = s.length();
    if (len % 2 == 1) return 0;
    java.util.LinkedList<Integer> toSkip = java.util.LinkedList<Integer>();
    for (int i = 0; i < len - 1; i++) {
        if (toSkip.contains(i)) continue;
        char c = s.charAt(i);
        int otherCharIndex = s.substring(i + 1).indexOf(c);
        if (otherCharIndex == -1) return 0;
        toSkip.add(i);
        toSkip.add(otherCharIndex + i + 1);
    }
    return 1;
}