Examples:
Input: str = “aaaad”
Output: 1
// “aaaad” is a anagram of a palindrome “aadaa”
Input: str = “abcd”
Output: 0
// “abcd” is not a anagram of any palindrome.
A Simple Solution is to take the input string, try every possible rotation of it and return true if a anagram is a palindrome. If no rotation is palindrome, then return false. But this approach is very lengthy and has exponential time complexity (O(n!)).
A palindrome can be broken into two halves. where in the first half is the reverse of second half. In case of odd length of strings, we have to ignore the middle character.
So for every character in the first half, there is a corresponding matching character in the second half. This indicates that all the characters in a string must occur even number of times except for one which appears in the middle of the string.
public static boolean checkPalindrome(String input) { int [] count = new int[26]; for( int i = 0; i < input.length(); i++ ) { char ch = input.charAt(i); count[ch-'a']++; } int oddOccur = 0; for( int cnt:count ) { if( oddOccur > 1) // more than 1 char should have odd frequency return false; if( cnt%2 == 1 ) oddOccur++; } return true; }
private static int checkNumberOfPalindromeAnags(String input){
if(input.length()==1)
return 1;
int[] char_set = new int[26]; //assuming that only english alphabets would be used
for(int i=0;i<input.length();i++){
char_set[input.charAt(i) - 'a']++;
}
int numberOfOddChars = 0;
int numOfPalins = 0;
for(int i=0;i1){
return 0;
}
if(char_set[i]!=0 && char_set[i]%2==0){
numOfPalins++;
}
else if(char_set[i]%2==1){
if(char_set[i]>1)
numOfPalins++;
numberOfOddChars++;
}
}
return numOfPalins;
}
If “rubbur” is palindrome or not??
your code will fail for this..
odd occurrence is acceptable just for one alphabet at max which exactly was checked above
static boolean palindrom(String a)
{
a=a.toLowerCase();
boolean res=false;
char[] ch=a.toCharArray();
for(int i=0;i<a.length();i++)
{
if(ch[i]==ch[a.length()-i-1])
{
res=true;
}
}
return res;
}
str1 = “abcbcba”
# function to check if a string can be converted into Palindrome or not.
def check(str1):
len1 = len(str1)
flag = True
if len1 == 0 or len1 == 1:
return flag
dict1 = {}
for i in range (0,len1):
if str1[i] in dict1:
dict1[str1[i]] += 1
else:
dict1[str1[i]] = 1
count = 0
for keys,values in dict1.items():
if (values%2) != 0:
count += 1
if count > 1:
flag = False
return flag,dict1
flag,dict1 = check(str1)
#Function to check if a string is a Palindrome or not
def check_palin(palin):
len1 = len(palin)
s = “”
for i in range(0,len1):
j = len1-1-i
s = s + palin[j]
if s == palin:
return True
else:
return False
#Function to convert a string into a Palindrome.
def convert(dict1,str1):
palin = “”
len1 = len(str1)
if len1 == 0:
return palin
if len1 == 1 or len1 == 2:
return str1
len2 = len(dict1)
s1 = “”
s2 = “”
s3 = “”
for keys,values in dict1.items():
if values%2 == 0:
val = values/2
for i in range(0,val):
s1 = s1 + keys
s3 = keys + s3
else:
val = values
for i in range(0,val):
s2 = s2+keys
palin = s1+s2+s3
flag = check_palin(palin)
if flag == True:
return palin
else:
print “What the fuck”
if flag == True:
palin = convert(dict1,str1)
print (“yes the given string ‘%s’ can be convered to Palindrome. Here it is ‘%s’” %(str1,palin))
else:
print (“Sorry the given string ‘%s’ cannot be converted into a Palindrome” %(str1))
Due to this problem . I lost my interview today .
Here is a simple solution that struck to my mind after the interview .
Since we have to look into any combination of string . What will be the case when given String can’t be palindrome?
Ans – If it contains more than 1 odd no. of characters ..
In all other cases there will be any anagram of a string that will be palindrome .
So, if my string contains more than 1 odd no. of characters it won’t have any anagram as palindrome . It it does not contain it will be palindrome for at least one anagram .
Why not just use the features of modern languages?
bool is_palindrome(word)
return word == word.reversed()