Anagram of a palindrome
[+57] [10] Dimitri
[2011-12-09 14:50:37]
[ java algorithm ]
[ http://stackoverflow.com/questions/8447222/anagram-of-a-palindrome ] [DELETED]

I just had a technical job interview and in this process I had to solve this problem:

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

``````"kayak",
"Rats live on no evil star",
"Able was I ere I saw Elba.
``````

A string A is an anagram of a string B if A can be obtained from B by rearranging the characters. For example, in each of the following pairs one string is an anagram of the other:

``````"mary" and "army",
"rocketboys" and "octobersky",
``````

Write a function:

class Solution { public int isAnagramOfPalindrome(String S); }

that, given a non-empty string S consisting of N characters, returns 1 if S is an anagram of some palindrome and returns 0 otherwise.

Assume that:

``````N is an integer within the range [1..100,000];
string S consists only of English lower-case letters (a-z).
``````

For example, given S = "dooernedeevrvn", the function should return 1, because "dooernedeevrvn" is an anagram of the palindrome "neveroddoreven". Given S = "aabcba", the function should return 0.

Complexity:

``````expected worst-case time complexity is O(N);
expected worst-case space complexity is O(1) (not counting the storage required for input arguments).
``````

I totally failed the interview. I was not ready for those kind of questions but I still want to know the solution. My idea was to create 2 utility functions `isAnagram` which checks if String A is a anagram of String B and `createPalindrom` which creates a palindrom from a given String :

``````public class Solution {
public int isAnagramofPalindrom(String s){
if(isAnagram(s, createPalindrom(s))) return 1;
return 0;
}

public boolean isAnagram(String A, String B){
boolean yes = false ;
for( int i = 0; i < A.lenth(); i++){
yes = yes && exist(A.chartAt(i), B); //I know this is not optimized
}
return yes;
}

public boolean exist(char c, String b){
boolean found = true;
int i = 0;
while( found = (b.chartAt(i) != c)){
i++;
}
return found;
}

public String createPalindrom(String s){
//?????
}

}
``````

My problem was how to create the palindrom. Maybe, I get this wrong or maybe I had a bad approach of this problem. What is your point and how should I solve this problem?

(29) `I was not ready for those kind of questions ` who is? Who doesn't this for a living? ;) - Peter Lawrey
Just a side note: `yes = yes && exist(A.chartAt(i), B);` would not execute `exist(A.chartAt(i), B);` anymore while `yes` is false due to the shortcut operator `&&` - you might want `&` instead (just one char). - Thomas
@Thomas, euh I dont understand why I wont execute? - Dimitri
@Dimitri There was an error in my comment: it won't execute while `yes` is false and thus will never execute. This is the case due to the shortcut operator `&&` which defines that both operands have to be true. Since `yes` is the first operand it will be evaluated first and if it is false the entire expression can't be true. Thus the second operand (`exist(A.chartAt(i), B)`) will never be evaluated - it can't change the result of the expression. The operator `&` will not cause this shortcut behavior, so write `yes = yes & exist(A.chartAt(i), B);` instead. - Thomas
(2) Btw, `boolean yes ;` inside a method won't even compile. You have to initialize local variables. - Thomas
@Thomas Totally correct. Thanks for your answer. I will correct that rapidly - Dimitri
(1) Talking about palindromes gets hard^H^H^H^H interesting only when an actual language is involved :). - Kos
@Kos stackoverflow.com/questions/8450097/… is what I thought the question was at first, (except I thought handling the anagrams was also required) which seemed really hard for an interview. I thought I'd ask it as it's own question. - psr
To make it a little harder, you can try getting O(n) time and truly O(1) space, independent of the alphabet size (solendil's solution requires O(alphabet size) space). - jonderry
Also see my related (but different) question: stackoverflow.com/questions/2033903/… - Andreas Bonini
Well this one REALLY blew my mind until I realized it didn't have to re-arranged into proper English words. It's that sort of false assumption that would kill me in an interview. Adding that requirement, and grammar, would make this one a really scary interview question. - Philip
One more thing: please, do not use a possible variable value as variable name: `yes` as a `boolean` having a `false` value makes no sense, in the same way as you'd never write `int two = 3` - Alberto
@Philip yeah - the bit at the beginning about palindromes as english sentences is a bit scary and throws you off - but all you need to take from this part is that a palindrome string just a mirror image of its characters, about the middle character in the string. Also I imagine if they said something like 'take as long as you want' to complete this, then there'd be a few people still sitting there an hour later. - dodgy_coder
[+136] [2011-12-09 14:54:46] solendil [ACCEPTED]

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.

(1) Pretty sure this is the simplest and most efficient solution. Your first step O(N) could build up a dictionary containing Key('a') = Value(3) entries determining the number of character occurrences. Then, for an O(1) finish, ensure the conditions you stated are met. - Craig Otis
The placement of characters should also be checked. The string may turn out to be a palindrome, but not an anagram. - Daniel Gabriel
(1) @DanielGabriel if it's a palindrome then it is by definition an anagram (of itself). - Graham Borland
@DanielGabriel An interesting point. Depends on your definition of an anagram: If the string is a palindrome, is it not automatically an anagram of a palindrome? - Craig Otis
(41) You don't need to check the evenness of the String. You just need to check there is at most one odd counted letter. - Peter Lawrey
(1) @Peter Lawrey - good point, if there is exactly one odd counted character then the string will always be odd and the odd character goes in the middle of the palindrome. - dbenham
Peter - thanks for the comments. I think sometimes the hardest part about being a developer is truly understanding the problem. i too went about this like the questioner did, thinking it much more complex, and doing it in multiple steps - kind of a trick question in that sense... way to be keen on solving the puzzle. - one.beat.consumer
See, here's my problem with this solution: It involves words. I'd be stuck on the problem of wanting to thrash the person who wrote the question. A palindrome is a word or phrase which reads the same backwards as forwards. An anagram is a word or phrase which contains all the same letter as another word or phrase. It's not merely a rearrangement of letters. - Hack Saw
(2) craig DanielGabriel: it doesn't depend much on the definition. Since the question doesn't require the sentences to be made out of valid words, in the unlikley case that the interviewer meant "anagram" to exclude trivial anagrams (which is the normal english meaning, but I'd expect in a programming context the default to be to include them), any palindrome will be an anagram of a different palindrome unless its length <=3 or all the non-central letters are the same. - Jack V.
@HackSaw The problem defines what a palindrome and an anagram are for the purpose of this problem and gives examples. Fair enough, I think. It allows one to develop the algorithm easily in a couple minutes. If you bring in the notion of words into it, you end up developing a very complex program that could easily take months. (And before you say "I can do it in ten", realize that there are languages like Thai where words are not separated by spaces or punctuation and require heuristics) and require word lists and other materials, and if you want to handle typos... The problem is fine as is. - Sylverdrag
@Sylverdrag: The difficulty is that the definitions affect how you read the problem. I agree that they redefine the words clearly, my concern is that in a quick read, the redefinition causes cognitive dissonance. This is important because it doesn't take a lot of rewrite to make the problem clearer, but the time spent puzzling out what is really meant is costly. If you leave it ambiguous with intent, that's one thing, but I doubt there is that level of intent here. - Hack Saw
(1) @HackSaw I think it is on purpose. They could have just as easily said "write a function that takes a string input and determines if each character occurs an even number of times (one exception allowed). If so return true, otherwise return false." Same problem, far easier to code. But this is from a recruitment interview and it looks like want to see how the candidate converts a plain English problem into an algorithm. That's a fair enough requirement if they want programmers to interact with less technically minded personnel, or -god forbid- clients. - Sylverdrag
Just did this question for an interview, though I am afraid I got everything right except to ensure that there was only 1 odd letter in a alpha/frequency count. Hopefully I get some points for being mostly right? - David
Solved by definition +1 - Khaled A Khunaifer
1
[+20] [2011-12-09 14:56:38] Peter Lawrey

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.
``````

(2) Does this satisfy the O(1) space requirement? It could be argued that the bit set requires a entry for every different letter in the input string, which could be O(n) worst case. - Qwerky
(5) In the worst case its every possible letter which is 26 as stated or 65536 in the most extreme case. Either way its a fixed size based on the problem, not the input. - Peter Lawrey
You could use an `int` in this case and toggle bits and count the number of bits set yourself, but I don't see the point. ;) - Peter Lawrey
(1) The counter argument is that O(26) == O(1)? I like it. - Qwerky
(1) For time complexity, the factor is ignored. O(one billion * n + one trillion) = O(n); - Peter Lawrey
Input: "neverodf doreven". Result: Exception in thread "main" java.lang.IndexOutOfBoundsException: bitIndex < 0: -65 at java.util.BitSet.flip(BitSet.java:198) - Bhesh Gurung
(2) In the OP, `string S consists only of English lower-case letters (a-z)` You can allow spaces (and characters above) by changing the `'a'` to `' '` - Peter Lawrey
That works. Sorry forgot about the [a-z] assumption. - Bhesh Gurung
2
[+14] [2011-12-09 17:37:24] Ilmari Karonen

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.

Once I (finally!) understood the question, this was the answer I came up with. I think Peter Lawrey's answer is basically the same, and has the advantage of being more readable and expandable; but as you say, I cannot imagine Java being able to optimize a BitSet to be as quick as this code. - Darren Cook
Perfect solution! I would replace `for (...;...;...) cycle` with `for-each` cycle: `for (char c: s.toCharArray()) b ^= 1 << (c - 'a');`. This also eliminates the need of `char[] c` array. - Prizoff
@Prizoff: Yeah, good suggestion. I learned Java so long ago that I sometimes forget it has such fancy features as for-each loops these days... - Ilmari Karonen
3
[+3] [2011-12-09 14:54:23] Victor Sorokin

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.

(1) care to explain -1? - Victor Sorokin
Not exactly twice - for example, "akayaka" - this is a palindrome, but does not match your solution for finding one. @solendil's solution of making sure that each character (except one) occurs an even number of times (for an odd-length string) is correct - Craig Otis
`25 cells, one cell per English alphabet's letter.` - aren't there 26 letters? - Thomas
@Thomas Thank you - Victor Sorokin
Why 25 cells? I thought there were 26 letters in the English alphabet. ;) - Peter Lawrey
(aside: There are 26 letters in the English alphabet.) And, you can do it with 26 bits in a bitfield, which (for the win) is a single 32-bit integer, so you can test for even'ness with `if 0 == letters`, before having to count bits to make sure only 1 bit is still set. In Java, those optimizations might be harder or pointless, though; not sure. - BRPocock
@BRPocock The condition can be `letters & (letters-1) == 0`, for extra leetness. - Daniel Fischer
@DanielFischer That is awesome. Totally using that in assembler, too. `lda value;beq true;dec .a;and value;beq true` to test for 0 or 1 bit set, instead of rotating bits and `bmi` … I don't think I've ever seen that method used, I wonder why‽ - BRPocock
@BRPocock No idea why, it's the standard test for powers of 2 (edge cases have to be considered (0, -2^31 if signed)) among bit-fiddlers. I see it regularly, not only in my own code. - Daniel Fischer
@DanielFischer Wrong precedence (which Java inherits from C). You need `(letters & (letters-1)) == 0` - Jim Balter
@JimBalter Oops, right, thanks. Every now and then I forget about the wrong precedence. Too late to edit, now, unfortunately. - Daniel Fischer
4
[+3] [2011-12-09 15:07:38] Barry

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

uff , did not realize that already there are so many answers. When i started typing the answer , there was just one answer before :) - Barry
So far it seems you are the only / one of few who takes into account even lengthy words as possible palindromes :-) - EricG
@EricG Eh? All the other answers take even length words into account ... even the one with a -7 score that says that only even-length words can be palindromes. - Jim Balter
oops when they say "if even string is odd" I read as "only if" then there will be a chance of positive result. But it's an additional if but nvm you're right xD. - EricG
(1) Thanks for writing out the basic idea behind the problem. Much easier to grasp than looking straight at code. - Garreh
5
[+2] [2011-12-09 14:55:56] Gabriel Negut

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.

6
[0] [2012-05-13 18:01:18] paraneec

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.

the question is in java language, so there is no such primitive type - `unsigned java`; and you can not do `!temp` if temp is int. - Prizoff
7
[0] [2013-03-24 06:20:56] Khaled A Khunaifer

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);
}
}

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

return true;
}
``````

Now compare your long solution, with solution proposed by Ilmari Karonen, which after replacing for into for-each will take only 3 (!) rows. - Prizoff
(1) His solution runs faster but its limited, while my solution supports all Unicode symbols (and can be generalized to any type\collection) .. - Khaled A Khunaifer
8
[-1] [2013-07-23 10:27:27] Akeel Nazir

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;

}
``````

The OP wanted a solution in java, not javscript. - Manuel
"isPalindrome" can't be the answer to the question "isAnagramOfPalindrome". - Will Ness
9
[-9] [2011-12-09 15:39:50] Roberto Chiaretti

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;
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;