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

7 Thoughts on “Check if Any Anagram of a String is Palindrome or Not

  1. Pratyu on August 14, 2014 at 1:23 am said:

    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 .

  7. LarsN on April 3, 2018 at 10:11 pm said:

    Why not just use the features of modern languages?

    bool is_palindrome(word)
    return word == word.reversed()

Leave a Reply to Deepali Agarwal Cancel 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