## Overview

In many interview questions, what they are looking for is a simple solution to an apparently complex problem. Unfortunately, the solutions are usually obvious if you know the solution, but very hard to come up with in an interview situation. ;)

## Anagram of Palindrome

Write a method to test if a String is an anagram of a palindrome. The method should have O(n) time complexity and O(1) space complexity. You can assume all letters are between ' ' (space) and 'z'. Assume only letters matter and case is ignored.

e.g.
"kayak"
"Rats live on no evil star"
"A man, a plan, a canal, Panama"
"Doc, note: I dissent. A fast never prevents a fatness. I diet on cod."

## The solution

A brute force approach is to generate anagrams and test if they are a palindromes. This is not required. All you need to test is if the String is the sort of string which can be turned into a palindrome.

Sample solution available HERE

1. Is it OK to assume that O(k) space complexity is acceptable, where k is the size of the alphabet?

2. First I'd ask if I could do it programming in Scala ;-)

def palindromAnagram(s: String) =
s.groupBy((c: Char) => c).values
.filterNot(_.length % 2 == 0)
.size <= 1

Group all the same characters together.
Filter all those with an even number of characters.
Find out if we are left with one or less odd character.

(Okay, okay, so it doesn't really satisfy the O(1) space complexity requirement)

3. @aix, as long as it fixed for the problem and doesn't depend on the length of the message, I would call it O(1).

@Karadoc, That's pretty cool and shows the general idea. DOes it filter only letters a to z and ignore case? (Something I imagine is also pretty easy in scala)

Once we have a solution, we could compare the performance, ;)

5. @wonkydonky The garbage produced should also be O(1). Can you think of a better collection for storing 0 and 1's? ;)

6. What about a string array of "true" and "false" values ;)

7. I was thinking something more efficient (and a natural choice in this situation)

8. Hmm. boolean storage requirements are VM dependent right? - it could well be represented as int's under the hood. What else could I use?
Even if there is a more efficient solution I'm not sure why my solution's garbage isn't O(1).

9. @wonkydonky, Using Character could be creating an object for each character, however in this specific case those are cache. It could be better to use char type.

For the collection I would use BitSet which in this case wraps a single long value.

11. Thanks for the response. The Character object was a little redundant.

Uses 2 bytes, a char and an int for storage and does two passes of the string.

12. v1.1 : http://pastebin.com/AfLDjC7v
1 int , 1 char , 1 byte, one pass

13. Nice fei, but you still need 2 ints (one for the array). However I was too hasty as my second byte should actually be an int :-/

14. And i'm missing a bit of logic in my second pass. Damm this is addictive.

15. wait a sec. the checking method should have two args: source palindrome and an anagram candidate to validate, right?

otherwise it makes no sense

16. @ikcileibp I state at the end of the question this is not required, you only need to determine if the string could be turned into a palindrome, not find what the palindrome is.

17. @fel since you like low level answers, for bonus points, can you write "if('a'<=c && c<='z')" with one comparison instead of two. (Can be slightly faster;)

18. @fel For extra obscurity; how might using (c & 31) help combine the two if clauses.

19. This is my first attempt at this problem. I'm going to try to make a better solution than this.

package tp;
import java.util.Enumeration;
import java.util.Scanner;

import com.sun.org.apache.xalan.internal.xsltc.runtime.Hashtable;

public class AOP {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println("Enter input:");
Scanner scan=new Scanner(System.in);
String input=scan.nextLine();
input=input.toLowerCase();
Hashtable alphabets=new Hashtable();
for ( int i=0;i1 )
{ System.out.println("Input string is not an anagram of a palindrome ");
break;
}
}

}

}

str.equals(new StringBuffer(str).reverse().toString());

21. I'm not able to correctly submit my code. I don't know what might be wrong, but the full code ain't getting published. Some formatting issue? Any other way through which I can publish?

22. @luiX_
If you input as kaka, it would fail, when it should not

23. @szcukg just forgot the "anagram" part... xDDD

Was thinking just about checking string's a palindrome :P

24. @Peter Lawrey : damned! You were absolutely right;)

2 int, 1 char, one pass, one test solution :
http://pastebin.com/jhZZ30Zm

25. @szcukg Unfortunately the code in the comment is considered to be HTML so you need to put &lt; instead of < :(

26. @fel, this fails for characters between 'Z' and 'a' (it counts them)

BTW: What if you were to use (1 << c) instead of (1 << (c & 31)) ? ;)

27. O(n) space to radix sort, but I guess it is O(1) extra space if you do an in place radix sort.

O(alphabet size) to do (parity) counting sort on a bitvector.

A bit trie with a parity counter at the leaves would be elegant for sparse alphabets. If your alphabet is fixed a priori then you could write off the construction of the bit trie as preprocessing.

28. (untested) (parity) counting sort version
https://gist.github.com/1477344

29. @Peter Lawrey

Sorry, i didn't get your single comparison trick :(.
However, despite my solution counts characters between 'Z' and 'a', the bitmask discard them before the bitcount, therefore only letters matters ; (btw, are you sure the isAnagramOfAPalindrome test fails because my unit tests are still ok)

using 1<<c is very tricky (with 32 bits int ;) ). I made some performance test in order to compare (1<<c) and (1<<(c&31)) ; there is huge differences between jdk1.6 and 1.7 (64 bits version) but i miss time to investigate.

my new proposition :
http://pastebin.com/BtA6ydY3

30. @Chad Brewbaker In the palindrome examples on wikipedia, case is ignored and D matches with d.

31. @fel to do a range comparison in one compare you can try.

if (c + Integer.MIN_VALUE - 'A' <= 'z' + Integer.MIN_VALUE - 'A')

This maps 'A' to MIN_VALUE (any value less than this underflows to be close to MAX_VALUE) The compiler combines the constants. Note: Whether you add or subtract MIN_VALUE makes no difference. ;)

You're program would not work when there is an odd number of special characters, even when there are blank spaces and just one odd character.

33. @szcukg

Yeah '.' can be odd regardless of string length if you only have one sentence. You can fix that corner case by ignoring the parity of special characters, or always setting them to even.

@Peter if I remember my ASCII that is a simple bitwise AND. If you want to get really complicated you could give it a dictionary and list of allowable sentence grammars. Keeping that in O(n log n) let alone linear time would be extremely challenging. For example http://en.wikipedia.org/wiki/Buffalo_buffalo_Buffalo_buffalo_buffalo_buffalo_Buffalo_buffalo .

34. An anagram is a type of word, the result of rearranging the letters of a word or phrase to produce a new word or phrase, using all the original letters exactly once.

For example: orchestra can be rearranged into carthorse or cat can be rearranged into act.

We can find out the anagram strings using below algorithm:

public static boolean isAnagram(String str1, String str2) {
if (str1 == null || str2 == null) {
return false;
} else if (str1.length() != str2.length()) {
return false;
}

Map map = new HashMap();

for (int i = 0; i < str1.length(); i++) {
char characters = str1.charAt(i);
int charInStr1 = map.containsKey(characters) ? map.get(characters) : 0;
map.put(characters, ++charInStr1);
char charFromStr2 = str2.charAt(i);
int charsInRight = map.containsKey(charFromStr2) ? map.get(charFromStr2) : 0;
map.put(charFromStr2, --charsInRight);
}

for (int occurrences : map.values()) {
if (occurrences != 0) {
return false;
}
}
return true;
}