What is the best algorithm to find whether an anagram is of a palindrome?

Question

In this problem we consider only strings of lower-case English letters (a-z).

A string is a palindrome if it has exactly the same sequence of characters when traversed left-to-right as right-to-left. For example, the following strings are palindromes:

"kayak"

"codilitytilidoc"

"neveroddoreven"

A string A is an anagram of a string B if it consists of exactly the same characters, but possibly in another order. For example, the following strings are each other's anagrams:

A="mary" B="army" A="rocketboys" B="octobersky" A="codility" B="codility"

Write a function

int isAnagramOfPalindrome(String S);

which returns 1 if the string s is a anagram of some palindrome, or returns 0 otherwise.

For example your function should return 1 for the argument "dooernedeevrvn", because it is an anagram of a palindrome "neveroddoreven". For argument "aabcba", your function should return 0.

Answer 1

'Algorithm' would be too big word for it.

You can construct a palindrome from the given character set if each character occurs in that set even number of times (with possible exception of one character).
For any other set, you can easily show that no palindrome exists.

Proof is simple in both cases, but let me know if that wasn't clear.

Answer 2

In a palindrome, every character must have a copy of itself, a "twin", on the other side of the string, except in the case of the middle letter, which can act as its own twin.

The algorithm you seek would create a length-26 array, one for each lowercase letter, and start counting the characters in the string, placing the quantity of character n at index n of the array. Then, it would pass through the array and count the number of characters with an odd quantity (because one letter there does not have a twin). If this number is 0 or 1, place that single odd letter in the center, and a palindrome is easily generated. Else, it's impossible to generate one, because two or more letters with no twins exist, and they can't both be in the center.

Answer 3

I came up with this solution for Javascript. This solution is based on the premise that a string is an anagram of a palindrome if and only if at most one character appears an odd number of times in it.

function solution(S) {
    var retval = 0;
    var sorted = S.split('').sort(); // sort the input characters and store in 
                                     // a char array
    var array = new Array();

    for (var i = 0; i < sorted.length; i++) {

        // check if the 2 chars are the same, if so copy the 2 chars to the new
        // array
        // and additionally increment the counter to account for the second char
        // position in the loop.
        if ((sorted[i] === sorted[i + 1]) && (sorted[i + 1] != undefined)) {
            array.push.apply(array, sorted.slice(i, i + 2));
            i = i + 1;
        }
    }

    // if the original string array's length is 1 or more than the length of the
    // new array's length
    if (sorted.length <= array.length + 1) {
        retval = 1;
    }

    //console.log("new array-> " + array);
    //console.log("sorted array-> " + sorted);
    return retval;
}

Answer 4

i wrote this code in java. i don't think if its gonna be a good one ^^,

 public static int isAnagramOfPalindrome(String str){
     ArrayList<Character> a = new ArrayList<Character>();

     for(int i = 0; i < str.length(); i++){
         if(a.contains(str.charAt(i))){
             a.remove((Object)str.charAt(i));
         }
         else{
             a.add(str.charAt(i));
         }
     }
     if(a.size() > 1)
        return 0;
     return 1;
 }

Answer 5

Algorithm:

1. Count the number of occurrence of each character.

2. Only one character with odd occurrence is allowed since in a palindrome the maximum number of character with odd occurrence can be '1'.

3. All other characters should occur in an even number of times.

4. If (2) and (3) fail, then the given string is not a palindrome.

Answer 6

This adds to the other answers given. We want to keep track of the count of each letter seen. If we have more than one odd count for a letter then we will not be able to form a palindrome. The odd count would go in the middle, but only one odd count can do so.

We can use a hashmap to keep track of the counts. The lookup for a hashmap is O(1) so it is fast. We are able to run the whole algorithm in O(n). Here's it is in code:

if __name__ == '__main__':
    line = input()

    dic = {}
    for i in range(len(line)):
        ch = line[i]
        if ch in dic:
            dic[ch] += 1
        else:
            dic[ch] = 1

    chars_whose_count_is_odd = 0
    for key, value in dic.items():
        if value % 2 == 1:
            chars_whose_count_is_odd += 1

    if chars_whose_count_is_odd > 1:
        print ("NO")
    else:
        print ("YES")

Answer 7

I have a neat solution in PHP posted in this question about complexities.

class Solution { 

    // Function to determine if the input string can make a palindrome by rearranging it
    static public function isAnagramOfPalindrome($S) {

        // here I am counting how many characters have odd number of occurrences
        $odds = count(array_filter(count_chars($S, 1), function($var) {
            return($var & 1);
        }));
        // If the string length is odd, then a palindrome would have 1 character with odd number occurrences
        // If the string length is even, all characters should have even number of occurrences
        return (int)($odds == (strlen($S) & 1));
    }
}

echo Solution :: isAnagramOfPalindrome($_POST['input']);

It uses built-in PHP functions (why not), but you can make it yourself, as those functions are quite simple. First, the count_chars function generates a named array (dictionary in python) with all characters that appear in the string, and their number of occurrences. It can be substituted with a custom function like this:

$count_chars = array();
foreach($S as $char) {
    if array_key_exists($char, $count_chars) {
        $count_chars[$char]++;
    else {
        $count_chars[$char] = 1;
    }
}

Then, an array_filter with a count function is applied to count how many chars have odd number of occurrences:

$odds = 0;
foreach($count_chars as $char) {
    $odds += $char % 2;
}

And then you just apply the comparison in return (explained in the comments of the original function).

return ($odds == strlen($char) % 2)

Answer 8

This runs in O(n). For all chars but one, must be even. the optional odd character can be any odd number.

e.g. abababa

def anagram_of_pali(str):
    char_list = list(str)
    map = {}
    nb_of_odds = 0

    for char in char_list:
        if char in map:
            map[char] += 1
        else:
            map[char] = 1

    for char in map:
        if map[char] % 2 != 0:
            nb_of_odds += 1

    return True if nb_of_odds <= 1 else False

Answer 9

You just have to count all the letters and check if there are letters with odd counts. If there are more than one letter with odd counts the string does not satisfy the above palindrome condition.
Furthermore, since a string with an even number letters must not have a letter with an odd count it is not necessary to check whether string length is even or not. It will take O(n) time complexity:

Here's the implementation in javascript:

function canRearrangeToPalindrome(str)
{
    var letterCounts = {};
    var letter;
    var palindromeSum = 0;
    for (var i = 0; i < str.length; i++) {
        letter = str[i];
        letterCounts[letter] = letterCounts[letter] || 0;
        letterCounts[letter]++;
    }
    for (var letterCount in letterCounts) {
        palindromeSum += letterCounts[letterCount] % 2;
    }

    return palindromeSum < 2;
}

Answer 10

All right - it's been a while, but as I was asked such a question in a job interview I needed to give it a try in a few lines of Python. The basic idea is that if there is an anagram that is a palindrome for even number of letters each character occurs twice (or something like 2n times, i.e. count%2==0). In addition, for an odd number of characters one character (the one in the middle) may occur only once (or an uneven number - count%2==1). I used a set in python to get the unique characters and then simply count and break the loop once the condition cannot be fulfilled. Example code (Python3):

def is_palindrome(s):
  letters = set(s)
  oddc=0
  fail=False

  for c in letters:
      if s.count(c)%2==1:
          oddc = oddc+1

      if oddc>0 and len(s)%2==0:
          fail=True
          break
      elif oddc>1:
          fail=True
          break

  return(not fail)

Answer 11

While you can detect that the given string "S" is a candidate palindrome using the given techniques, it is still not very useful. According to the implementations given,

isAnagramOfPalindrome("rrss") would return true but there is no actual palindrome because:

A palindrome is a word, phrase, number, or other sequence of symbols or elements, whose meaning may be interpreted the same way in either forward or reverse direction. (Wikipedia)

And Rssr or Srrs is not an actual word or phrase that is interpretable. Same with it's anagram. Aarrdd is not an anagram of radar because it is not interpretable.

So, the solutions given must be augmented with a heuristic check against the input to see if it's even a word, and then a verification (via the implementations given), that it is palindrome-able at all. Then there is a heuristic search through the collected buckets with n/2! permutations to search if those are ACTUALLY palindromes and not garbage. The search is only n/2! and not n! because you calculate all permutations of each repeated letter, and then you mirror those over (in addition to possibly adding the singular pivot letter) to create all possible palindromes.

I disagree that algorithm is too big of a word, because this search can be done pure recursively, or using dynamic programming (in the case of words with letters with occurrences greater than 2) and is non trivial.

Answer 12

Here's some code: This is same as the top answer that describes algorithm.

  1 #include<iostream>
  2 #include<string>
  3 #include<vector>
  4 #include<stack>
  5 
  6 using namespace std;
  7 
  8 bool fun(string in)
  9 {
 10 int len=in.size();
 11 int myints[len ];
 12 
 13 for(int i=0; i<len; i++)
 14 {       
 15         myints[i]= in.at(i);
 16 }
 17 vector<char> input(myints, myints+len);
 18 sort(input.begin(), input.end());
 19 
 20 stack<int> ret;
 21 
 22 for(int i=0; i<len; i++)
 23 {
 24         if(!ret.empty() && ret.top()==input.at(i))
 25                 {
 26                 ret.pop();
 27                 }
 28         else{
 29         ret.push(input.at(i));
 30         }
 31 }
 32 
 33 return ret.size()<=1;
 34 
 35 }
 36 
 37 int main()
 38 {
 39 string input;
 40 cout<<"Enter word/number"<<endl;
 41 cin>>input;
 42 cout<<fun(input)<<endl;
 43 
 44 return 0;
 45 }

Answer 13

def is_anagram_of_palindrome(S):
    L = [ 0 for _ in range(26) ]
    a = ord('a')
    length = 0
    for s in S:
        length += 1
        i = ord(s) - a
        L[i] = abs(L[i] - 1)
    return length > 0 and sum(L) < 2 and 1 or 0