Check if Any Anagram of a String is Palindrome or Not

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

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

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation