# Check if Any Anagram of a String is Palindrome or Not

Examples:
Output: 1

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

### 6 Thoughts on “Check if Any Anagram of a String is Palindrome or Not”

1. 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;
}

2. If “rubbur” is palindrome or not??
your code will fail for this..

3. Ved Swarup on April 7, 2015 at 6:36 pm said:

odd occurrence is acceptable just for one alphabet at max which exactly was checked above

4. 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;
}

5. Deepali Agarwal on May 13, 2016 at 3:22 am said:

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

6. Aayush Singhal on May 17, 2017 at 10:35 pm said:

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 .