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?
Thx for your advice
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.
int
in this case and toggle bits and count the number of bits set yourself, but I don't see the point. ;) - Peter Lawrey
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
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.
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
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.
25 cells, one cell per English alphabet's letter.
- aren't there 26 letters? - Thomas
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
letters & (letters-1) == 0
, for extra leetness. - Daniel Fischer
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
(letters & (letters-1)) == 0
- Jim Balter
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.
unsigned java
; and you can not do !temp
if temp is int. - Prizoff
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;
}
I was not ready for those kind of questions
who is? Who doesn't this for a living? ;) - Peter Lawreyyes = yes && exist(A.chartAt(i), B);
would not executeexist(A.chartAt(i), B);
anymore whileyes
is false due to the shortcut operator&&
- you might want&
instead (just one char). - Thomasyes
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. Sinceyes
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 writeyes = yes & exist(A.chartAt(i), B);
instead. - Thomasboolean yes ;
inside a method won't even compile. You have to initialize local variables. - Thomasyes
as aboolean
having afalse
value makes no sense, in the same way as you'd never writeint two = 3
- Alberto